题目描述

[MEDIUM]

Given an integer array nums of unique elements, return all possible subsets (the power set).

The solution set must not contain duplicate subsets. Return the solution in any order.

Example 1:

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

Example 2:

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

Constraints:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
All the numbers of nums are unique.

思路

We can use backtracking (DFS) to generate all possible subsets.
At each element, we have two choices:

Include the current element.

Exclude the current element.

This gives us all 2^n subsets.

example

Let’s trace the call stack for nums = [1, 2, 3].

Step 1: Start
index = 0, current = []
result = [[]]

Step 2: Loop (i = 0)

Include 1 → current = [1], recurse with index = 1

Step 3: Inside that recursive call

Now loop starts again:

i = 1 → include 2 → current = [1,2]

recurse with index = 2

i = 2 → include 3 → current = [1,2,3]

recurse with index = 3 → end → add [1,2,3]

backtrack → remove 3 → [1,2]

backtrack → remove 2 → [1]

i = 2 → include 3 → current = [1,3]

recurse with index = 3 → add [1,3]

backtrack → remove 3 → [1]

loop ends → return up

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> re;

    void backtrack(int idx, vector<int>& nums, vector<int>& cur){
        re.push_back(cur);

        for(int i = idx; i < nums.size(); i++){
            cur.push_back(nums[i]);

            backtrack(i + 1, nums, cur);

            // exclude nums[i] (back track)
            cur.pop_back();
        }
    }

    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> cur;

        backtrack(0, nums, cur);
        return re;
    }
};