Ultra important.

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

1
2
3
4
5
6
7
8
9
10
11
12
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]
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
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> list = new ArrayList<>();
        dfs(list, new ArrayList<>(), nums, 0);
        return list;
    }
    
    public void dfs(List<List<Integer>> list, List<Integer> arr, int[] nums, int s) {
        list.add(new ArrayList<>(arr));
        System.out.println("added" + arr);
        System.out.println("s= " + s);
        
        for (int i = s; i < nums.length; ++i) {
            System.out.println("i= " + i);
            System.out.println("Entering for loop ---");
            arr.add(nums[i]);
            System.out.println("+++" + nums[i]);
            
            dfs(list, arr, nums, i+1);
            
            System.out.println("arr now:" + arr);
            
            System.out.println("dfs: " + s);
            arr.remove(arr.size() - 1);
            System.out.println("backtracking");
        }
    }
}

下面的输出可能更好理解程序是怎么运行的。关键：backtracking到什么时候？到下一步DFS能产生不同的subset的时候

Output:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
added[]
s= 0
i= 0
Entering for loop ---
+++1
added[1]
s= 1
i= 1
Entering for loop ---
+++2
added[1, 2]
s= 2
i= 2
Entering for loop ---
+++3
added[1, 2, 3]
s= 3
arr now:[1, 2, 3]
dfs: 2
backtracking
arr now:[1, 2]
dfs: 1
backtracking
i= 2
Entering for loop ---
+++3
added[1, 3]
s= 3
arr now:[1, 3]
dfs: 1
backtracking
arr now:[1]
dfs: 0
backtracking
i= 1
Entering for loop ---
+++2
added[2]
s= 2
i= 2
Entering for loop ---
+++3
added[2, 3]
s= 3
arr now:[2, 3]
dfs: 2
backtracking
arr now:[2]
dfs: 0
backtracking
i= 2
Entering for loop ---
+++3
added[3]
s= 3
arr now:[3]
dfs: 0
backtracking