leetcode--78--子集

题目：
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

题目链接：https://leetcode-cn.com/problems/subsets

思路：
1、解集里先放入第一个元素的子集，然后依次遍历剩下的元素，每一个元素和解集组合成一个新的集合加到原解集里面
2、python中需要注意列表中的列表append的问题，它会改变原始的列表，因此需要注意使用深拷贝

Python代码：

import copy

class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        if not nums:
            return [[]]

        ans = [[nums[0]],[]]
        for item in nums[1:]:
            temp = []
            ans_cp = copy.deepcopy(ans)
            for a in ans_cp:
                a.append(item)
                temp.append(a)
            ans.extend(temp)
        return ans

C++代码：

class Solution {

public:
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<vector<int>> ret;
        vector<int> temp;

        if (nums.empty()){
            return ret;
        }

        ret.push_back(temp);
        temp.push_back(nums[0]);
        ret.push_back(temp);
    
        for (size_t i=1; i<nums.size(); i++){
            int item = nums[i];
            vector<vector<int>> ret_cp(ret);  // 深拷贝一份ret
            for(vector<int> re : ret_cp){
                re.push_back(item);
                ret.push_back(re);
            }
        }
        return ret;
    }
};