Problem description:

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
13
14
Example:

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

Solution:

DFS + backtracking.
This question is very similar to 39. Combination Sum.

1
2
3
4
5
6
7
8
9
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def dfs(res, tmp, nums):
            res.append(tmp)
            for i in range(len(nums)):
                dfs(res, tmp+[nums[i]], nums[i+1:])
        res = []
        dfs(res, [], nums)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        sort(nums.begin(), nums.end())
        backtrack(res, tmp, nums, 0);
        return res;
    }
    void backtrack(vector<vector<int>>& res, vector<int>& tmp, vector<int>& nums, int pos){
        res.push_back(tmp); //add every set into the result
        for(int i = pos; i < nums.size(); i++){
            tmp.push_back(nums[i]); //sequentially add every element in the result
            backtrack(res, tmp, nums, i+1);
            tmp.pop_back();
        }
    }
};