leetcode Subsets II

Subsets II 原題位址：

https://oj.leetcode.com/problems/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],
  []
]      

S中有重複元素，那麼就要避免S'+第一個2,和S'+第二個2相同的情況(S'∈S)，那麼維護一個boolean數組，表示某一進制素是否被選中，目前一個元素和目前元素相同，而且前一個元素沒有被選中的情況下，那麼這個元素就不去選他，就可以避免這種情況。

public class Solution {
    private List<List<Integer>> ans = new LinkedList<List<Integer>>();
	public List<List<Integer>> subsetsWithDup(int[] S) {
		if (S == null || S.length == 0)
			return ans;
		LinkedList<Integer> temp = new LinkedList<Integer>();
		Arrays.sort(S);
		int[] flag = new int[S.length];
		search(temp, S, 0, flag);
		return ans;
	}
	
	private void search(LinkedList<Integer> temp, int[] S, int idx, int[] flag) {
		if (idx == S.length) {
			LinkedList<Integer> list = (LinkedList<Integer>) temp.clone();
			ans.add(list);
			return;
		}
		if (idx == 0 || S[idx] != S[idx-1] || (S[idx] == S[idx-1] && flag[idx-1] == 1)) {
			temp.add(S[idx]);
			flag[idx] = 1;
			search(temp, S, idx+1, flag);
			flag[idx] = 0;
			temp.pollLast();
		}
		search(temp, S, idx+1, flag);
	}
}