---
# System prepended metadata

title: 'LeetCode #78 [Subsets](https://leetcode.com/problems/subsets/)'
tags: [DFS, Recursion, LeetCode, Medium]

---

###### tags: `LeetCode` `Medium` `DFS` `Recursion`
# LeetCode #78 [Subsets](https://leetcode.com/problems/subsets/)
### (Medium)

給定一個無重複數字的整數數組 nums, 返回所有可能的子集（冪集）。

解決方案集不得包含重複的子集。 可以任何順序回傳答案。


---

這題需考慮兩個變數: 組合長度與組合起始數, 因此需要兩個for迴圈來負責遍歷。

當暫存數組的長度等於目標組合長度時即可直接將暫存數組儲存至答案數組中。


---
```
class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        // n: numbers of each combination, 0,1,2,...,n-1
        // pos: element starts from
        vector<int> tmp;
        vector<vector<int>> ans;
        for(int i=0;i<=nums.size();i++){//組合長度
            dfs(nums, i, 0, tmp, ans);
        }
        return ans;
    }
    void dfs(vector<int>& nums, int n, int pos, vector<int>& tmp, vector<vector<int>> &ans){
        if(tmp.size()==n){
            ans.push_back(tmp);
            return;
        }
        for(int i=pos;i<nums.size();i++){//組合起始值
            tmp.push_back(nums[i]);
            dfs(nums, n, i+1, tmp, ans);
            tmp.pop_back();
        }
    }
};
```