[LintCode/LeetCode] Subsets & Subsets II

tracy 发布于2019-08-14 14:26 / 1221人阅读

Subsets Problem

Given a set of distinct integers, return all possible subsets.

Notice

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

Example

If S = [1,2,3], a solution is:

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

Challenge

Can you do it in both recursively and iteratively?

Solution

class Solution {
    public ArrayList> subsets(int[] nums) {
        ArrayList> res = new ArrayList<>();
        if (nums == null || nums.length == 0) return res;
        ArrayList cur = new ArrayList<>();
        Arrays.sort(nums);
        dfs(nums, cur, res, 0);
        return res;
    }
    public void dfs(int[] nums, ArrayList cur, ArrayList> res, int index) {
        if (index > nums.length) return;
        res.add(new ArrayList (cur));
        for (int i = index; i < nums.length; i++) {
            cur.add(nums[i]);
            dfs(nums, cur, res, i+1);
            cur.remove(cur.size()-1);
        }
    }
}

Subsets II Problem

Given a list of numbers that may has duplicate numbers, return all possible subsets

##Notice

Each element in a subset must be in non-descending order.
The ordering between two subsets is free.
The solution set must not contain duplicate subsets.
Have you met this question in a real interview? Yes

Example

If S = [1,2,2], a solution is:

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

Challenge

Can you do it in both recursively and iteratively?

Solution

class Solution {
    public ArrayList> subsetsWithDup(ArrayList S) {
        ArrayList> res = new ArrayList<>();
        Collections.sort(S);
        ArrayList cur = new ArrayList<>();
        dfs(S, cur, res, 0);
        return res;
    }
    public void dfs(ArrayList S, ArrayList cur, ArrayList> res, int index) {
        if (index > S.size()) return;
        res.add(new ArrayList (cur));
        for (int i = index; i < S.size(); i++) {
            if (i != index && S.get(i) == S.get(i-1)) continue;
            cur.add(S.get(i));
            dfs(S, cur, res, i+1);
            cur.remove(cur.size()-1);
        }
    }
}

专线服务混合云 Subsets II quartus ii ii6

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65006.html

【LC总结】回溯 (Subsets I II/Permutation I II/Combinatio

摘要：不同数包含重复数为的时候，表示在外层的循环正在被使用，所以当前循环遇到为一定要跳过。对当前循环要添加的数组，在添加当前元素后进行递归，递归之后要将当前元素的使用标记改为，表示已经使用和递归完毕，然后再将这个元素从的末位删除。 Subsets Problem Given a set of distinct integers, nums, return all possible subse...

tuomao 2019-08-14 15:53 评论0 收藏0
leetcode90. Subsets II

摘要：题目要求可以先参考关于的这篇博客再看接下来的内容。思路一链表的形式我们可以通过例子，，，来说明。在递归中我们会将起始下标后的值依次加入当前结果集，并将结果集加入结果集数组中。如果遇到重复的数字，则继续遍历下一个数字，直至遍历结束。题目要求 Given a collection of integers that might contain duplicates, nums, retur...

PascalXie 2019-08-15 10:48 评论0 收藏0
leetcode-90. Subsets II

摘要：题目描述注意题目解读找出所有的子集。思路确定子集的来源，遍历原始列表，每一个元素都往已有的子集列表里边添加，同时添加到已有的子集中去，产生新的子集。类似于动态规划思想，依赖于之前的东西产生现在的东西。题目描述 Given a collection of integers that might contain duplicates, nums, return all possible ...

lijinke666 2019-07-30 17:22 评论0 收藏0
Subsets 系列 Leetcode解题记录

摘要：写这个系列是因为纪念一下去年的今天，就是年的月号，刷题第一天，今天是一周年纪念日。排除，就是返回一空的。复杂度分析算法课讲过，这个复杂度是指数次，能实现出来就行了，没法优化。复杂度分析不分析了，反正指数次。 Subsets 写这个系列是因为纪念一下去年的今天，就是2015年的9月14号，刷题第一天，今天是一周年纪念日。当时只敢做easy还得抄答案的我想啥时候能做上medium啊，事到如...

gityuan 2019-08-14 14:41 评论0 收藏0
[Leetcode] Subset 子集

摘要：深度优先搜索复杂度时间空间递归栈空间思路这道题可以转化为一个类似二叉树的深度优先搜索。另外需要先排序以满足题目要求。新的集合要一个新的，防止修改引用。 Subset I Given a set of distinct integers, nums, return all possible subsets. Note: Elements in a subset must be in n...

hzc 2019-08-14 12:23 评论0 收藏0