力扣Leetcode 78 | 子集（Subsets）

约定不等于承诺〃 2022-12-15 02:56 131阅读 0赞

参考：  
[https://leetcode-cn.com/problems/subsets/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by–10/][https_leetcode-cn.com_problems_subsets_solution_xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by_10]  
[https://leetcode-cn.com/problems/subsets/solution/hui-su-python-dai-ma-by-liweiwei1419/][https_leetcode-cn.com_problems_subsets_solution_hui-su-python-dai-ma-by-liweiwei1419]

### 目录 ###

*  1 迭代法
 *  2 递归(回溯算法)
 *  3 位运算

# 1 迭代法 #

从条件上入手，先只考虑给定数组的 1 个元素的所有子数组，然后再考虑数组的 2 个元素的所有子数组 … 最后再考虑数组的 n 个元素的所有子数组。求 k 个元素的所有子数组，只需要在 k - 1 个元素的所有子数组里边加上 nums \[ k \] 即可。

例如 nums \[1 , 2, 3\] 的遍历过程：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center]  
java代码：

public List<List<Integer>> subsets(int[] nums) { 
        List<List<Integer>> ans = new ArrayList<>();
        ans.add(new ArrayList<>());//初始化空数组
        for(int i = 0;i<nums.length;i++){ 
            List<List<Integer>> ans_tmp = new ArrayList<>();
            //遍历之前的所有结果
            for(List<Integer> list : ans){ 
                List<Integer> tmp = new ArrayList<>(list);
                tmp.add(nums[i]); //加入新增数字
                ans_tmp.add(tmp);
            }
            ans.addAll(ans_tmp);
        }
        return ans;
    }

python代码：

class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            res=[[]]
            for i in nums:
                l=len(res)
                for j in range(l):
                    c=res[j].copy()
                    c.append(i)
                    res.append(c)
            return res

class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            res = [[]]
            for i in nums:
                res = res + [[i] + num for num in res]
            return res

# 2 递归(回溯算法) #

需要判断结果集是所有的节点还是所有的叶子节点。  
另外，递归过程，也分为前序遍历和后序遍历，理解两者的区别。

理解递归的终止条件。  
回溯搜索的问题，状态空间很大，能剪枝就尽量剪枝。

参考，讲解的特别好，特别是视频：

# 3 位运算 #

class Solution:
        def subsets(self, nums: List[int]) -> List[List[int]]:
            size = len(nums)
            n = 1 << size
            res = []
            for i in range(n):
                cur = []
                for j in range(size):
                    if i >> j & 1:
                        cur.append(nums[j])
                res.append(cur)
            return res

[https_leetcode-cn.com_problems_subsets_solution_xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by_10]: https://leetcode-cn.com/problems/subsets/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--10/
[https_leetcode-cn.com_problems_subsets_solution_hui-su-python-dai-ma-by-liweiwei1419]: https://leetcode-cn.com/problems/subsets/solution/hui-su-python-dai-ma-by-liweiwei1419/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hb2Vyc29uZw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/374d120433a840efadf565612dc05299.png