Massive Algorithms: Leetcode 90

Leetcode 90 - Subsets II

https://leetcode.com/problems/subsets-ii/
Leetcode: Subsets II
Given a collection of integers that might contain duplicates, S, return all possible subsets.
Note: Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.
For example, If S = [1,2,2], a solution is:

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

Iterative Version
https://leetcode.com/discuss/11905/simple-iterative-solution
https://discuss.leetcode.com/topic/3601/simple-iterative-solution/7
https://discuss.leetcode.com/topic/39672/share-my-2ms-java-iteration-solution-very-simple-and-short/2

If we want to insert an element which is a dup, we can only insert it after the newly inserted elements from last step.

public List<List<Integer>> subsetsWithDup(int[] num) {
  Arrays.sort(num);
  List<List<Integer>> ret = new ArrayList<>();
  ret.add(new ArrayList<Integer>());

  int size = 0, startIndex;
  for(int i = 0; i < num.length; i++) {
    startIndex = (i >= 1 && num[i] == num[i - 1]) ? size : 0;
    size = ret.size();
    for(int j = startIndex; j < size; j++) {
      List<Integer> temp = new ArrayList<>(ret.get(j));
      temp.add(num[i]);
      ret.add(temp);
    }
  }
  return ret;
}

public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList();
        ans.add(new ArrayList()); // add []
        for (int i = 0, prev = 0; i < nums.length; i++) {
            int size = ans.size();
                for (int j = (i == 0 || nums[i] != nums[i - 1]) ? 0 : prev; j < size; j++) {
                    List<Integer> cur = new ArrayList(ans.get(j));
                    cur.add(nums[i]);
                    ans.add(cur);
                }
            prev = size;
        }
        return ans;
    }

https://leetcode.com/discuss/15/how-to-adapt-subsets-i-solution-to-subsets-ii-problem
https://leetcode.com/discuss/17832/accepted-java-iterative-solution
public List<List<Integer>> subsetsWithDup(int[] num) { List<List<Integer>> subsets = new ArrayList<List<Integer>>(); subsets.add(new ArrayList<Integer>()); if (null == num || num.length == 0) return subsets; quickSort(num, 0, num.length - 1); int j, lastLength = 0; for (int i = 0; i < num.length; i++) { if (i != 0 && num[i] == num[i - 1]) j = lastLength; else j = 0; lastLength = subsets.size(); for (; j < lastLength; j++) { ArrayList<Integer> temp = (ArrayList<Integer>) subsets.get(j); temp = (ArrayList<Integer>) temp.clone(); temp.add(num[i]); subsets.add(temp); } } return subsets; }
https://leetcode.com/discuss/11864/48ms-solution-with-subset-construction-method
http://blog.csdn.net/zyfo2/article/details/8897695

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
    Arrays.sort(num);
    ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
    ret.add(new ArrayList<Integer>());

    int start = 0;
    for(int i = 0; i < num.length; i++)
    {
        int size = ret.size();
        for(int j = start; j < size; j++)
        {
            ArrayList<Integer> sub = new ArrayList<Integer>(ret.get(j));
            sub.add(num[i]);
            ret.add(sub);
        }
        if(i < num.length - 1 && num[i + 1] == num[i]) //
            start = size;
        else
            start = 0;
    }
    return ret;
}

http://www.programcreek.com/2013/01/leetcode-subsets-ii-java/

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
 if (num == null)
  return null;
 Arrays.sort(num);
 ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
 ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>();
 for (int i = num.length-1; i >= 0; i--) {
  //get existing sets
  if (i == num.length - 1 || num[i] != num[i + 1] || prev.size() == 0) {
   prev = new ArrayList<ArrayList<Integer>>(result);

  }
  //add current number to each element of the set
  for (ArrayList<Integer> temp : prev) {
   temp.add(0, num[i]);
  }
  //add each single number as a set, only if current element is different with previous
  if (i == num.length - 1 || num[i] != num[i + 1]) {
   ArrayList<Integer> temp = new ArrayList<Integer>();
   temp.add(num[i]);
   prev.add(temp);
  }
  //add all set created in this iteration
  result.addAll(prev);
 }
 //add empty set
 result.add(new ArrayList<Integer>());
 return result;
}

https://leetcode.com/discuss/17832/accepted-java-iterative-solution

http://blog.csdn.net/linhuanmars/article/details/24613193
就是每当遇到重复元素的时候我们就只把当前结果集的后半部分加上当前元素加入到结果集中，因为后半部分就是上一步中加入这个元素的所有子集，上一步这个元素已经加入过了，前半部分如果再加就会出现重复。所以算法上复杂度上没有提高，反而少了一些操作，就是遇到重复时少做一半，不过这里要对元素集合先排序，否则不好判断重复元素。同样的还是可以用递归和非递归来解，不过对于重复元素的处理是一样的

http://blog.csdn.net/cinderella_niu/article/details/42293601

1）如果当前处理的元素没有出现过，则把前面得到的所有集合加上该元素，集合数翻倍。

2）如果当前处理的元素出现过，那么我们只把上一轮处理过的集合加上该元素（即上一轮添加了当前重复数字的集合）。比如，添加第二个2时，我们只把上一轮添加过2的集合{1,2}、{2}再添加一个2到结果中，其他集合不懂，{1}和{}是从上一层直接继承下来的，不做处理。由于我们是顺序添加集合到ret中的，所以处理过的集合总是排在ret的后面位置。

1. 需要维护两个变量，上一次处理的数字，即将要进行操作的子集数量。

2.如果本次处理元素重复，将不更新opResNum,则 ret.size() - opResNum不等于0，我们只处理后面的res.size() - opResNum个集合。

   vector<vector<int> > subsetsWithDup(vector<int> &S) {
        int len = S.size();
        sort(S.begin(), S.end());
        vector<vector<int>> ret(1);
        //上一个处理的数字，即将要进行操作的子集数量
        int last = S[0], opResNum = 1;
        
        for(int i = 0; i < S.size(); i++)
        {
            //如果本次处理数字和上次不重复，更新这两个变量
            if(S[i] != last)
            {
                last = S[i];
                opResNum = ret.size();
            }
            
            //如果出现重复数字，本次处理的集合数和上次一样，即只处理上次处理过的集合。resSize - opResNum，如果opResNum不等于res.size(),则只处理上次处理过的集合。由于迭代是顺序添加的，所以上次处理过的集合一定排在ret的末尾res.size() - opResNum个。
            int retSize = ret.size();
            for(int j = retSize - 1; j >= retSize - opResNum; j--)
            {
                ret.push_back(ret[j]);
                ret.back().push_back(S[i]);
            }
        }
        
        return ret;
    }

DFS, Recursive Version
https://leetcode.com/problems/subsets-ii/discuss/30158/Standard-DFS-Java-Solution
http://www.jiuzhang.com/solutions/subsets-ii/

    public ArrayList<ArrayList<Integer>> subsets(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> list = new ArrayList<Integer>();
        if(num == null || num.length ==0) {
            return result;
        }
        Arrays.sort(num);
        subsetsHelper(result, list, num, 0);

        return result;
    }

    private void subsetsHelper(ArrayList<ArrayList<Integer>> result,
        ArrayList<Integer> list, int[] num, int pos) {

        result.add(new ArrayList<Integer>(list));
        
        for (int i = pos; i < num.length; i++) {
            if ( i != pos && num[i] == num[i - 1]) {
                continue;
            }    
            list.add(num[i]);
            subsetsHelper(result, list, num, i + 1);
            list.remove(list.size() - 1); //good
        }
    }

https://leetcode.com/problems/subsets-ii/discuss/30158/Standard-DFS-Java-Solution

public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null || nums.length == 0){
            return res;
        }
        Arrays.sort(nums);
        List<Integer> curr = new ArrayList<>();
        dfs(nums, 0, res, curr);
        return res;
    }
    private void dfs(int[] nums, int index, List<List<Integer>> res, List<Integer> curr){
        res.add(new ArrayList<>(curr));
        if(index == nums.length){
            return;
        }
        Set<Integer> visited = new HashSet<Integer>();
        for(int i = index; i < nums.length; i++){
            if(visited.add(nums[i])){
                curr.add(nums[i]);
                dfs(nums, i + 1, res, curr);
                curr.remove(curr.size() - 1);
            } 
        }
    }

http://blog.welkinlan.com/2015/07/17/subsets-i-subsets-ii-leetcode-java/

    public ArrayList<ArrayList<Integer>> subsetsWithDup(ArrayList<Integer> S) {

        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        result.add(new ArrayList<Integer>());

        if (S == null || S.size() == 0) {

            return result;

}

        Collections.sort(S);

        helper(result, S, new ArrayList<Integer>(), 0);

        return result;

}

    private void helper(ArrayList<ArrayList<Integer>> result, ArrayList<Integer> S, ArrayList<Integer> cur, int i) {

        for (int j = i; j < S.size(); j++) {

            if (j > i && S.get(j) == S.get(j - 1)) {

                continue;

}

            cur.add(S.get(j));

            result.add(new ArrayList<Integer>(cur));

            helper(result, S, cur, j + 1);

            cur.remove(S.get(j)); // use this: cur.remove(cur.size() - 1);

}

}

https://leetcode.com/discuss/54544/very-simple-and-fast-java-solution

public List<List<Integer>> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> each = new ArrayList<>();
    helper(res, each, 0, nums);
    return res;
}
public void helper(List<List<Integer>> res, List<Integer> each, int pos, int[] n) {
    if (pos <= n.length) {
        res.add(each);
    }
    int i = pos;
    while (i < n.length) {
        each.add(n[i]);
        helper(res, new ArrayList<>(each), i + 1, n);
        each.remove(each.size() - 1);
        i++;
        while (i < n.length && n[i] == n[i - 1]) {i++;}
    }
    return;
}

The Basic idea is: use "while (i < n.length && n[i] == n[i - 1]) {i++;}" to avoid the duplicate. For example, the input is 2 2 2 3 4. Consider the helper function. The process is:

each.add(n[i]); --> add first 2 (index 0)
helper(res, new ArrayList<>(each), i + 1, n); --> go to recursion part, list each is <2 (index 0)>
while (i < n.length && n[i] == n[i - 1]) {i++;} --> after this, i == 3, add the element as in subset I

http://shanjiaxin.blogspot.com/2014/02/subsets-ii-leetcode.html

http://www.cnblogs.com/springfor/p/3879853.html

当有重复元素出现就只对当前这个元素走一起，其他重复元素跳过1 public static void dfs(int[] S, int start, int len, ArrayList<Integer> item,ArrayList<ArrayList<Integer>> res){

2         if(item.size()==len){
3             res.add(new ArrayList<Integer>(item));
4             return;
5         }
6         for(int i=start; i<S.length;i++){
7             item.add(S[i]);
8             dfs(S, i+1, len, item, res);
9             item.remove(item.size()-1);
10             while(i<S.length-1&&S[i]==S[i+1])//跳过重复元素
11                 i++;
12         }
13
14     }
15
16     public static ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
17         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
18         ArrayList<Integer> item = new ArrayList<Integer>();
19         if(S.length==0||S==null)
20             return res;
21
22         Arrays.sort(S);
23         for(int len = 1; len<= S.length; len++)
24             dfs(S,0,len,item,res);
25
26         res.add(new ArrayList<Integer>());
27
28         return res;
29     }

1. 在添加res时候判断是否res中已经存过该item了。没存过的才存保证子集唯一性。-not efficent

1 public static void dfs(int[] S, int start, int len, ArrayList<Integer> item,ArrayList<ArrayList<Integer>> res){
2         if(item.size()==len){
3             if(!res.contains(item))
4                 res.add(new ArrayList<Integer>(item));
5             return;
6         }
7         for(int i=start; i<S.length;i++){
8             item.add(S[i]);
9             dfs(S, i+1, len, item, res);
10             item.remove(item.size()-1);
11         }
12
13     }
14
15     public static ArrayList<ArrayList<Integer>> subsetsWithDup(int[] S) {
16         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
17         ArrayList<Integer> item = new ArrayList<Integer>();
18         if(S.length==0||S==null)
19             return res;
20
21         Arrays.sort(S);
22         for(int len = 1; len<= S.length; len++)
23             dfs(S,0,len,item,res);
24
25         res.add(new ArrayList<Integer>()); //don't forget empty set
26
27         return res;
28     }

Code from http://jelices.blogspot.com/2014/03/leetcode-subsets-ii.html

public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> solution = new ArrayList<List<Integer>>();
        subsetsWithDup(num, 0, new ArrayList<Integer>(), solution);
        return solution;
    }
    
    public void subsetsWithDup(int[] num, int index, ArrayList<Integer> tempSolution, List<List<Integer>> solution) {
        if(index == num.length)
        {
            solution.add((List<Integer>)tempSolution.clone());
            return;
        }
        
        //Do not add element num[i]
        int value = num[index];
        int i= index;
        while(i<num.length && num[i]==value)
            i++;
        subsetsWithDup(num, i, tempSolution, solution);
            
        //Add element num[i]
        tempSolution.add(num[index]);
        subsetsWithDup(num, index+1, tempSolution, solution);
        tempSolution.remove(tempSolution.size()-1);
    }

http://blog.csdn.net/cinderella_niu/article/details/42293601
我们知道处理第三个元素2时，因为前面已经出列一次2，所以第三层中，我们只在添加过2的结合{1,2}和{2}再添加2，而没有在集合{1}，{}中添加2（画叉的那些分支），假设下面还有一个2，我们将只会在第四层包含两个2的集合{12,2}和{2,2}中添加2，其他都不添加。因此DFS, 如果当前处理的数字，在前面出现了k次（原集合S中),那么我们要处理的集合中必须包含k个该元素。否则会出现重复的集合
Code from http://fisherlei.blogspot.com/2013/01/leetcode-subsets-ii.html
vector<vector<int> > subsetsWithDup(vector<int> &S) {
vector<vector<int> > result;
vector<int> output;
if(S.size() ==0) return result;
result.push_back(output);
sort(S.begin(), S.end());
generateSub(S, 0, result, output);
}
void generateSub(vector<int> &s, int step, vector<vector<int> > &result, vector<int>& output)
{
for(int i = step;i<s.size(); i++ )
{
output.push_back(s[i]);
result.push_back(output);
if(i< s.size()-1)
generateSub(s, i+1, result, output);
output.pop_back();
while(i<s.size()-1 && s[i] == s[i+1])
i++;
}
}
X. Bit Algorithm
https://discuss.leetcode.com/topic/12706/java-solution-using-bit-manipulation

The idea is using every bit to represent one element in the set. The total number is 2 to num.length. Then we need to avoid duplicates. After we sort the array, the same number will be adjacent to each other.

For example the set is {1,1,1}. We can get subset {} and {1} first. That's great.
Then we need to pay attention. Suppose we have a subset x, which including the second 1 but not the first 1, x is a duplicate.
That's why I write the predicate:
if(j>0&&num[j]==num[j-1]&&(i>>(j-1)&1)==0){
illegal=true;
break;
}

    public List<List<Integer>> subsetsWithDup(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> lists = new ArrayList<>();
        int subsetNum = 1<<num.length;
        for(int i=0;i<subsetNum;i++){
            List<Integer> list = new ArrayList<>();
            boolean illegal=false;
            for(int j=0;j<num.length;j++){
                if((i>>j&1)==1){
                    if(j>0&&num[j]==num[j-1]&&(i>>(j-1)&1)==0){
                        illegal=true;
                        break;
                    }else{
                        list.add(num[j]);
                    }
                }
            }
            if(!illegal){
               lists.add(list); 
            }

        }
        return lists;
    }

https://leetcode.com/discuss/8769/my-solution-using-bit-masks

public List<List<Integer>> subsetsWithDup(int[] num) { //Sort the input Arrays.sort(num); int numberSets = 1 << num.length; List<List<Integer>> solution = new LinkedList<>(); for(int i = 0; i<numberSets; i++){ List<Integer> subset = new LinkedList<Integer>(); for(int j = 0; j< num.length; j++){ if((i & (1 << j)) > 0){ subset.add(num[j]); } } if(!solution.contains(subset)) solution.add(subset); } return solution; }

if(!solution.contains(subset))
    solution.add(subset);

This is too slow.

You can use Set<List<Integer>> instead of List<List<Integer>> to speed up checking for duplicate subsets.

TODO: https://cheonhyangzhang.wordpress.com/2015/09/28/90-leetcode-java-subsets-ii-medium/

    public List<List<Integer>> subsetsWithDup(int[] nums) {

        List<List<Integer>> res = new ArrayList<List<Integer>> ();

        List<Integer> item = new ArrayList<Integer>();

        if(nums.length==0||nums==null)

            return res;

        Arrays.sort(nums);

        for(int len = 1; len<= nums.length; len++)

               dfs(nums,0,len,item,res);

        res.add(new ArrayList<Integer>());

        return res;

}

    public static void dfs(int[] nums, int start, int len, List<Integer> item,List<List<Integer>> res){

        if(item.size()==len){

            res.add(new ArrayList<Integer>(item));

            return;

}

        for(int i=start; i<nums.length;i++){

            item.add(nums[i]);

            dfs(nums, i+1, len, item, res);

            item.remove(item.size()-1);

            while(i<nums.length-1&&nums[i]==nums[i+1])//skip duplicate element

                i++;

        }//for

}

Also refer to http://codeganker.blogspot.com/2014/04/subsets-ii-leetcode.html

http://blog.hyoung.me/cn/2017/02/subsets/

在上一题的基础之上，我们现在考虑数组中有重复元素的情况。同样，我们先可以通过一个例子[1,2,2]来观察 DFS 搜索的过程。

DFS Search in [1,2,2]

我们可以发现。重复子集的出现是在当前可搜索集合中有重复元素造成的，于是我们只需要在上一题的基础之上做出一点改变：若当前元素与可搜索集合中已经搜索过的元素重复，那就跳过它。在这种情况下，就必须要先对整个数组进行排序了，然后查重就很简单了，与当前元素的前一个元素进行比较即可。


vector<vector<int> > subsets(vector<int> &nums) {

vector<vector<int>> results;

vector<int> subset;

sort(nums.begin(), nums.end());

dfsHelper(nums, 0, subset, results);



return results;

}



void dfsHelper(vector<int>& nums, int startIndex, vector<int>& subset, 

vector<vector<int>>& results) {

results.push_back(subset);



for (int i = startIndex; i < nums.size(); ++i) {

if (i > startIndex && nums[i] == nums[i-1])

continue;



subset.push_back(nums[i]);

dfsHelper(nums, i + 1, subset, results);

subset.pop_back();

}

}

其中需要注意的地方就是i > startIndex的约束条件了。因为startIndex代表着当前可搜索集合的起始位置，所以当i == startIndex，并不「存在」前一个元素。

Read full article from My Own Notes: Leetcode: Subsets II

Leetcode 90 - Subsets II

Labels

Popular Posts