Posts Tagged ‘duplicate’
比如 {1, 1, 1, 2, 3}，x = 3, 结果就是{111}{12}{3}。这个题挺难想的，和上一题又不一样。正常stack，把1push进去，然后直接在2上recurse x=2的（因为1只能用一次）。这样一直做到x==0。这样就会有重复：当stack pop空了之后，回到第二个1上，又开始push，那stack的第0个又是1了，刚才已经做过stack第0个是1的一遍了（左边的一遍肯定包括了最多种的情况），所以现在再把1放里面就会重复。所以要在做“要不要在当前layer试一下下一个数？”的决定的时候，要看“下一个数和当前数是否相等？因为当前数已经做过了，同一层layer说明是同一个position，再放当前数就会重复）。
总结：
- combination/set: 用stack，因为长度不固定。
- permutation: 用int[]，keep一个pos pointer。
- 主函数里面不要循环，就一个以初始值call副函数的语句就行。
- 副函数是循环里面call自己。
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
Stack<Integer> path = new Stack<Integer>();
combinationSum(num, target, 0, path, result);
return result;
}
private void combinationSum(int[] arr, int target, int start, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
if (target == 0) {
ArrayList<Integer> list = new ArrayList<Integer>();
list.addAll(path);
result.add(list);
return;
}
for (int i = start; i < arr.length; i++) {
if (arr[i] > target)
return;
path.push(arr[i]);
combinationSum(arr, target - arr[i], i + 1, path, result);
path.pop();
//do we want to place arr[i + 1] at the same position arr[i] has been?
while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
i++;
}
}
}
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}
- {}, {1}, {2}, {12}
- {}, {1}, {2}, {12} 这时要是还往{}和{1}里面插2就会产生重复。所以要想办法把他们skip过去。skip到哪为止呢？毕竟还是想往{2}和{12}里插的。
- 所以是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;
}
平时的permutation有一个boolean used[]，如果arr[i]在之前的layer里用过了，就不能再用了。比如{1, 2, 1}，到pos2的时候，看即使arr[2]是“1”，但是这个1不是第一个用过的1，所以还可以放在当前pos当中。但是在pos0的时候，如果想用第二个1，就不行了（当前pos已经有人用过数字1了，即使用的是arr[0]不是当前想用的arr[2]，但是是同一个数字就不行），所以skip掉。因此，算法是“在每个position存一个hashset记录在这个position放过那些数字，若是以前放过了，这次就别放了。“
public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (num.length == 0)
return result;
permute(num, 0, new int[num.length], new boolean[num.length], result);
return result;
}
private void permute(int[] num, int pos, int[] path, boolean[] used, ArrayList<ArrayList<Integer>> result) {
if (pos == path.length) {
result.add(convertToIntegerList(path));
return;
}
Set<Integer> layerTried = new HashSet<Integer>();
for (int i = 0; i < num.length; i++) {
if (!layerTried.contains(num[i]) && used[i] == false) {
path[pos] = num[i];
used[i] = true;
permute(num, pos + 1, path, used, result);
layerTried.add(num[i]);
used[i] = false;
}
}
}
Lexi's Leetcode solutions 