[LintCode/LeetCode] Subsets & Subsets II

tracy 發布于2019-08-14 14:26 / 1336人閱讀

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);
        }
    }
}

云服務器 GPU云服務器 Subsets II quartus ii ii6

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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