1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#对于全排列问题
    class  Solution {
    public List<List<Integer>>  permute(int[] nums){
        int len= nums.length;
        List<List<Integer>> res=new ArrayList<>();
        if (len==0) return res;

        Deque<Integer> path=new ArrayDeque<>(len);
        boolean[] used=new boolean[len];
        dfs(nums,len,0,path,used,res);
        return res;
    }
   
    private void dfs(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) {
        if (depth==len) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i=0;i<len;i++){//注意这里是i=0,表示每一次遍历都是遍历整个数组中的元素
            if (!used[i]){
                path.add(nums[i]);
                used[i]=true;

                dfs(nums, len, depth+1, path, used, res);

                used[i]=false;
                path.removeLast();
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#组合问题
    class Solution {
    public List<List<Integer>> combine(int n, int k) {

        List<List<Integer>> res = new ArrayList<>();
        if (n == 0) return res;
        int[] nums = new int[n];//先将其转换为数组
        for (int i = 1; i <= n; i++) {
            nums[i - 1] = i;
        }


        Deque<Integer> path = new ArrayDeque<>();
//采用深度优先遍历的方式，begin表示从剩下的元素中挑选元素，例如在[1,2,3,4]中先选1后，只能够在[2,3,4]中挑选元素
        dfs(nums, 0, k, 0, path, res);
        return res;

    }

    private void dfs(int[] nums, int depth, int k, int begin, Deque<Integer> path, List<List<Integer>> res) {
        if (depth == k) {//depth表示path中的元素个数
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = begin; i < nums.length; i++) {//使用begin设置下一轮的搜索起点，这样能保证解是无序的

            path.add(nums[i]);

            dfs(nums, depth + 1, k, i + 1, path, res);//因为使用过的元素是不能够再次使用的，所以是i+1；
            //如果使用过的元素是能够再次使用的，则为i

            path.removeLast();

        }
    }
}