[leetcode] Subsets 1, 2 | 给一个数组，输出所有升序的不重复的subsets

Posted by: lexigrey on: October 8, 2013

• In: leetcode
• Leave a Comment

subset 1:  array本身都是distinct number，所以往里一个一个插不用担心重复。{}, 放第一个，放第二个。。

//inintialize a {}, keep inserting, mark as used (distinct nums)
public ArrayList<ArrayList<Integer>> subsets(int[] S) {
    Arrays.sort(S);
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
    for (int i = 0; i < S.length; i++) {
        ArrayList<ArrayList<Integer>> temp = new ArrayList<ArrayList<Integer>>();
        for (ArrayList<Integer> prevSubset : result) {
            ArrayList<Integer> newSubset = new ArrayList<Integer>();
            newSubset.addAll(prevSubset);
            newSubset.add(S[i]);
            temp.add(newSubset);
        }
        result.addAll(temp);
    }
    return result;
}

subset 2————————————-
先sort，然后往后加。重点是怎么保证不重复？比如array[] = {1, 2, 2}

1. {}
2. {}, {1}
3. {}, {1}, {2}, {12}
4. {}, {1}, {2}, {12} 这时要是还往{}和{1}里面插2就会产生重复。所以要想办法把他们skip过去。skip到哪为止呢？毕竟还是想往{2}和{12}里插的。
5. 所以是arr[i] == arr[i + 1]的时候，不要往arr[i]之前那一层插了。要往i这一层新插的里面插。

public ArrayList<ArrayList<Integer>> subsetsWithDup(int[] num) {
  Arrays.sort(num);
  ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    result.add(new ArrayList<Integer>());
  int start = 0;
  for (int i = 0; i < num.length; i++) {
    int prevSize = result.size();
    //上一层的size，是数字可以用来循环，避免modification exception
    for (int j = start; j < prevSize; j++) {
      ArrayList<Integer> newSubset = new ArrayList<Integer>();
      newSubset.addAll(result.get(j));
      newSubset.add(num[i]);
      result.add(newSubset);
    }
    if (i + 1 < num.length && num[i] == num[i + 1])
      start = prevSize;
      //i + 1那层越过i - 1这层的所有subsets，因为第i层已经往i - 1层的所有subsets里插过了
    else
      start = 0;
  }
  return result;
}

Tags: duplicate, hard, math, subsets/permutation