Archive for October 9th, 2013
If n = 4 and k = 2, a solution is:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
趁热打铁，这个题和上两道相比简单了不少，因为是固定长度所以不用stack了，用int[]加一个position variable。每次在这个pos上一个一个试数，每确定一个就在下一个pos处recurse。
public ArrayList<ArrayList<Integer>> combine(int n, int k) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (k <= 0 || n < 1)
return result;
populateResult(1, n, 0, result, new int[k]);
return result;
}
private void populateResult(int startNum, int endNum, int pos,
ArrayList<ArrayList<Integer>> result, int[] path) {
if (pos == path.length) {
ArrayList<Integer> combination = new ArrayList<Integer>();
convertArrayToList(path, combination);
result.add(combination);
return;
}
for (int i = startNum; i <= endNum; i++) { //i is using which number
path[pos] = i;
populateResult(i + 1, endNum, pos + 1, result, path); //use next
//number on next position
//as i++, use next number on same position
}
}
比如 {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++;
}
}
}
- In: leetcode
- 7 Comments
比如{2, 3, 6, 7}，x = 7，组合就是{2, 2, 3}和{7}。不能有重复，且必须是sorted order。
这个是标准DFS，一定要记住。先sort array，然后试图用2，用了2之后x相当于只剩5，然后下一层递归再用2，用到没法再用为止（当前值比x还大）。失败后stack pop出来，再试着在前面用了2, 2, 2的条件下用3， 挂，pop出2，在22的条件下用3，正好，输出。然后再pop一个2，再用3， {2, 3}，再用下一个3。。在脑子里想一下和树的dfs的图是一样的。
public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
Stack<Integer> path = new Stack<Integer>();
combinationSum(candidates, 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) //这时候break可以保证不要再查后面那些越来越大的
return;
path.push(arr[i]);
combinationSum(arr, target - arr[i], i, path, result); //start永远不会越界，所以一开始不用check
path.pop();
}
}
Lexi's Leetcode solutions 