个人记录-LeetCode 78. Subsets

问题:
Given a set of distinct integers, nums, return all possible subsets.

Note: The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

这个问题基本上就是LeetCode 77. Combinations的变种,
其实就是给定1个数组,然后求出从中取出0个、1个、2个…….n个数组成的所有排列。

代码示例:

public class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> rst = new ArrayList<>();

        if (nums == null || nums.length < 1) {
            return rst;
        }

        rst.add(new ArrayList<>());

        List<List<Integer>> temp;
        for (int i = 1; i <= nums.length; ++i) {
            temp = combine(nums, i);
            rst.addAll(temp);
        }

        return rst;
    }

    //以下基本是LeetCode 77的代码,略微改了下接口
    private List<List<Integer>> combine(int[] nInts, int k) {
        List<List<Integer>> rst = new ArrayList<>();

        List<Integer> curr = new ArrayList<>();
        for (int i = 0; i <= nInts.length-k; ++i) {
            combineInner(rst, nInts, i, curr, k);
        }

        return rst;
    }

    private void combineInner(List<List<Integer>> rst, int[] nInts, int next, List<Integer> curr, int sz) {
        List<Integer> newList = new ArrayList<>(curr);
        newList.add(nInts[next]);

        if (newList.size() == sz) {
            rst.add(newList);
            return;
        }

        for (int i = next+1; i <= nInts.length - (sz - newList.size()); ++i) {
            combineInner(rst, nInts, i, newList, sz);
        }
    }
}

个人觉得这个问题,在分析完LeetCode 77后,10分容易想到答案。
但如果没有见过LeetCode 77,直接来解的话,对拆分问题的能力还是有较高要求的。

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 个人记录-LeetCode 78. Subsets

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡