78 Subsets

78. Subsets​
1. Question
Given a set of distinct integers,nums, return all possible subsets (the power set).
Note:The solution set must not contain duplicate subsets.
For example,
Ifnums=[1,2,3], a solution is:
1
[
2
  [3],
3
  [1],
4
  [2],
5
  [1,2,3],
6
  [1,3],
7
  [2,3],
8
  [1,2],
9
  []
10
]
Copied!
2. Implementation
(1) Backtracking
1
class Solution {
2
    public List<List<Integer>> subsets(int[] nums) {
3
        List<List<Integer>> res = new ArrayList<>();
4
        List<Integer> subset = new ArrayList<>();
5
        getSubsets(nums, 0, subset, res);
6
        return res;
7
    }
8
​
9
    public void getSubsets(int[] nums, int start, List<Integer> subset, List<List<Integer>> res) {
10
        res.add(new ArrayList<>(subset));
11
​
12
        for (int i = start; i < nums.length; i++) {
13
            subset.add(nums[i]);
14
            getSubsets(nums, i + 1, subset, res);
15
            subset.remove(subset.size() - 1);
16
        }
17
    }
18
}
Copied!
3. Time & Space Complexity
Backtracking: 时间复杂度O(2^n), 空间复杂度O(2^n)

77 Combinations

79 Word Search

Last modified 2yr ago

Copy link

Contents

78. Subsets

1. Question

2. Implementation

3. Time & Space Complexity

78. Subsets​

1. Question

2. Implementation

3. Time & Space Complexity

78. Subsets