【leetcode】子集

  • Post author:
  • Post category:其他


题目:

给定一组

不含重复元素

的整数数组

nums

,返回该数组所有可能的子集(幂集)。


说明:

解集不能包含重复的子集。


示例:

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

思路:

从题目中可以看出,当你求子集[1,2,3]的时候用到了子集[1,2],而求子集[1,2]又用到了子集[1]。所以我们可以发现,我们所求的每一个子集都用到了上一个子集,因此我们可以用递归算法来求。


首先求单个子集,

比如[1],然后作为参数进行递归得到第二个子集[1,2],然后一步步递归,得到所有子集。


注意要包括空集。


java代码:

class Solution {
   public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
       res.add(new ArrayList<>());
        if(nums ==null || nums.length ==0) {
            return res;
        }

        subsets(res, nums, new ArrayList<>(), 0);

        return res;
    }

    private void subsets(List<List<Integer>> res, int[] nums, ArrayList<Integer> list, int k) {
        for(int i=k;i<nums.length;i++) {
           list.add(nums[i]);
            res.add(new ArrayList<>(list));
            subsets(res, nums, list, i+1);
            list.remove(list.size()-1);
        }
    }
}



由于水平有限,博客中难免会有一些错误,有纰漏之处恳请各位大佬不吝赐教!


推荐阅读:


【leetcode】全排列


【leetcode】括号生成


【leetcode】电话号码的字母组合


【leetcode-

动态规划

】爬楼梯


– CSDN博客


【leetcode-

动态规划

】买卖股票的最佳时机


– CSDN博客


【leetcode-

动态规划

】最大子序和


【leetcode-

动态规划

】 不同路径


– CSDN博客


【leetcode-

动态规划

】打家劫舍


及时更新最新文章和学习资料,一起来学习:



版权声明:本文为kangbin825原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。