Leetcode 78. 子集（全排列的变形）

主要思路：因为本题说明数组中的元素互不相同，因此要求所有的子集，也就是讲数组里面的数进行组合就行，但是不能重复。

Python：

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ans = []
        tmp = []
        n = len(nums)
        def dfs(start: int):
            if start > n:
                return
            ans.append(tmp[:])
            for i in range(start, n):
                tmp.append(nums[i])
                dfs(i + 1)
                tmp.pop()
        dfs(0)
        return ans

C++：

class Solution {
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> tmp;
        vector<vector<int>> ans;
        int n = nums.size();
        function<void(int)> dfs = [&](int start) {
            if (start > n) {
                return;
            }
            ans.push_back(tmp[:]);
            for (int i = start; i < n; i ++) {
                tmp.push_back(nums[i]);
                dfs(i + 1);
                tmp.pop_back();
            }
        };
        dfs(0);
        return ans;
    }
};

值的一提的是，递归起点必须是 start（如果不是的话，那么很多元素会重复的选，造成子集重复），这样可以做到去重效果！！！！

加油！！！