46 Permutations

Leetcode

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]

Example 3:

Input: nums = [1]
Output: [[1]]

---

使用深度优先递归，每一位依次不断将剩余数组元素放入 list ，使用一个 boolean 数组标记数字是否使用过。

class Solution {
    List<List<Integer>> ret;
    List<Integer> list;
    boolean[] visited;
    public List<List<Integer>> permute(int[] nums) {
        ret=new LinkedList<>();
        list=new ArrayList<>();
        visited=new boolean[nums.length];
        dfs(nums, 0);
        return ret;
    }
    
    private void dfs(int[] nums, int index){
        if(index==nums.length){
            ret.add(new ArrayList<>(list));
            return;
        }
        
        for(int i=0;i<nums.length;++i){
            if(visited[i]) continue;
            list.add(nums[i]);
            visited[i] = true;
            dfs(nums, index+1);
            list.remove(index);
            visited[i] = false;
        }
    }
}