CombinationSumII [source code]
public class CombinationSumII {
static
/******************************************************************************/
class Solution {
final boolean DEBUG = false;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort (candidates);
List<List<Integer>> res_lss = new ArrayList<> ();
search (candidates, 0, target, res_lss, new ArrayDeque<> ());
return res_lss;
}
void search (int[] candidates, int index, int remain, List<List<Integer>> lss, Deque<Integer> accum) {
if (DEBUG) System.out.println ();
String header;
if (DEBUG) header = String.format ("index:(%d): %s remain:(%d), lss:%s, accum:%s", index, array (candidates, index), remain, lss, accum);
if (DEBUG) System.out.println (header);
if (remain == 0) {
if (DEBUG) System.out.println (wrap ("\tHIT>>>" + header, 91));
lss.add (new ArrayList<> (accum));
if (DEBUG) System.out.println ();
return;
}
if (index >= candidates.length) {
if (DEBUG) System.out.println ();
return;
}
int next = index;
while (next < candidates.length && candidates[next] == candidates[index])
next++;
int num = next - index, cur = candidates[index], i;
for (i = 0; i <= num && remain >= i * cur; i++) {
if (i > 0)
accum.push (cur);
if (DEBUG) System.out.printf ("\t%s >>> i:(%d), accum:%s >>>>>\n", header, i, accum);
search (candidates, next, remain - i * cur, lss, accum);
}
if (DEBUG) System.out.printf ("\t%s >>> i:(%d), %s\n", header, i, accum);
assert accum.size () >= i - 1;
for (int j = 0; j < i - 1; j++)
accum.pop ();
if (DEBUG) System.out.println ();
}
String array (int[] nums, int index) {
StringBuilder sb = new StringBuilder ("[");
for (int i = 0; i < nums.length; i++)
sb.append ((i == index ? wrap (nums[i] + "", 95) : nums[i]) + " ");
return sb.toString () + "]";
}
String wrap (String s, int code) {
return (char) 27 + "[" + code + "m" + s + (char) 27 + "[0m";
}
}
/******************************************************************************/
public static void main(String[] args) {
CombinationSumII.Solution tester = new CombinationSumII.Solution();
int[][][] inputs = {
{{1,1,1,1,2}}, {{4}},
{
{1,1,1,1},
{1,1,2},
}, // 1
{{10, 1, 2, 7, 6, 1, 5}}, {{8}},
{
{1, 7},
{1, 2, 5},
{2, 6},
{1, 1, 6}
}, // 2
{{2,2,2,3}}, {{5}},
{
{2,3},
}, // 3
};
for (int i = 0; i < inputs.length / 3; i++) {
int[] candidates = inputs[3 * i][0];
int target = inputs[3 * i + 1][0][0];
System.out.println (Printer.separator ());
List<List<Integer>> output = tester.combinationSum2 (candidates, target);
System.out.printf ("[%s] and %d -> %s, expected: \n%s\n",
Printer.array (candidates), target, output, Matrix.printMatrix (inputs[3 * i + 2])
);
}
}
}
第一题的变形, 虽然不可以reuse了, 但是现在可以有duplicate了; 其实是类似的, 就相当于人为的给之前的reuse次数加了一个上限; 不过这题最好还是不要改之前的算法来做, 还要单独count一次, 感觉有点笨? 但是可以写出来的肯定;
用Deque的时候, 记得默认的peek(无论是用于queue操作(add/remove/offer/poll)还是Stack操作(push/pop/peek)), 都是peek的First; 这个具体可以看bear上面的笔记; 以前吃过一次亏了;
大概写了一个算法, 发现对于duplicate的处理比我想象的复杂: 如果candidate有duplicate, 但是最后结果的combination里面又不允许有duplicate, 那么只是单纯的在保证了order之后在每一个位置进行binary的use or not use是不够的;
感觉还是没有掌握好, 一开始写了这个算法:
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort (candidates);
List<List<Integer>> res_lss = new ArrayList<> ();
search (candidates, 0, target, res_lss, new ArrayDeque<> ());
return res_lss;
}
void search (int[] candidates, int index, int remain, List<List<Integer>> lss, Deque<Integer> accum) {
if (remain == 0) {
lss.add (new ArrayList<> (accum));
return;
} else {
for (int i = index; i < candidates.length; i++) {
int j = i;
while (j < candidates.length && candidates[j] == candidates[i])
j++;
search (candidates, j, remain, lss, accum);
if (remain >= candidates[i]) {
accum.push (candidates[i]);
search (candidates, j, remain - candidates[i], lss, accum);
accum.pop ();
}
}
}
}
首先, 这个算法肯定是错的; 但是我认为这个算法错在应该是数少了, 但是实际上最后的结果是有大量的duplicate; 不知道是为什么;
在分析这个算法的过程中, 思考了一下最后结果的combination的去重, 到底是什么意思? 实际上, 应该就是, 比如我有4个1, 但是最后的combination里面, 你只要区分是有0个, 1个,2个,3个,4个1参与就行了; 对于2个1参与的情况, 无所谓到底是哪两个. 如果看透了这一点, 感觉这题好像还是用count的做法更加合理;
后来上面那个算法的毛病还是大概理解了, 我上面其实主要逻辑内部就已经是在移动index了, 结果在每一个iteration还故意加了一个for loop, 这个导致最后的行为非常的奇怪, 你有兴趣可以自己print反正最后就会导致比如2,2,2,3 find 5的话, 3会依此和每一个2进行配对;
后来写了上面这个代码; 还是太大意了; 我再次总结recursion debug print的时候的要点:
- 开头结尾必须new line; 这个看起来很trivial, 但是非常重要, 不然加上其他的print之后根本看不清楚一个iteration是从哪里到那里;
- premature exit也不要忘记;
- 每一个iteration开始可以先把header给存起来, 类似上面代码的; 这样后面可以调用;
- 一个进阶的技巧是可以print每一个iteration的level, 这个其实不难做, 只要保存一个global的int, 代表level, 然后每一个iteration记得increment和decrement就行了; 在iteration当中可以直接调用这个level_count来打印一个空格string放到header前面, 这样最后的trace就有tree结构了; 不过这个其实并不是必须的;
- 每一个recursive call entrace之前打印transition: 要包含当前iteration的header就可以了, 然后类似这里这样, 加一个符号代表是entry to next level;
- HIT或者update的节点, 记得打印, 记得包含header;
掌握了这些技巧, 而且要熟练掌握, 可以让我快速的debug一个recursion; 另外, wrap, printMatrix, index print array这些, 都要能够很快速的写出来;
另外, 这题最后一个调掉的bug, 花了很长时间: 主要原因是这题的undo不是那么trivial;
for (i = 0; i <= num; i++) {
if (remain >= i * cur) {
if (i > 0)
accum.push (cur);
search (candidates, next, remain - i * cur, lss, accum);
}
}
你能看出来这个做法有什么问题吗? 这个做法的问题其实是, 当i太大(超过remain)的时候, 我没有直接break, 而是完成的是一个类似continue的操作! 这样导致的后果, 是所有过大的i的iteration, 最后都让i++了; 这样最后我pop的时候(看上面代码)按照i的原来的值来进行pop就错了;
其实这个东西最简单的方式就是push之前先cache住原来的size, 然后后面按照size来pop就行了, 绝对不会错; 当然, 这里把这个bug给调出来还是好的;
最后的速度是23ms (59%), 可以接受;
另外, 一个总结, 我这里去重的方法, 其实是保证每一个number(包括其duplicate, sort之后是在一起的)局限在同一个iteration里面处理完; 这个level的fanning, 实际上fan出去的就是究竟pick了多少个, 而不是pick与否;
size-based or element-based backtracking
现在我终于知道我的方法和他们这种recursion里面有一个循环的方法的区别了:
- 我的方法, 一个level对应的是一个particular number, 对于这个number本身, 我们要不要, 要几个, 这个就是这个level向下fan out的原因;
- 他们的带循环的方法, 一个level对应的其实是path的size, 也就是类似于我们第一个取什么, 那么这个"什么", 对应的就是这个fanning;
没有editorial;
@lchen77 said in Java solution using dfs, easy understand:
public List<List<Integer>> combinationSum2(int[] cand, int target) {
Arrays.sort(cand);
List<List<Integer>> res = new ArrayList<List<Integer>>();
List<Integer> path = new ArrayList<Integer>();
dfs_com(cand, 0, target, path, res);
return res;
}
void dfs_com(int[] cand, int cur, int target, List<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList(path));
return ;
}
if (target < 0) return;
for (int i = cur; i < cand.length; i++){
if (i > cur && cand[i] == cand[i-1]) continue;
path.add(path.size(), cand[i]);
dfs_com(cand, i+1, target - cand[i], path, res);
path.remove(path.size()-1);
}
}
这个算法就是一个size based的写法; 这个写法其实一开始是真的看不懂的; 得自己大概用类似1,2,2,2,2,3这样的例子走走看; 走了一下大概理解了. 实际上这个题目, 虽然这个代码看起来简单, 而且看起来相对于之前那题的改动很小, 但是实际上背后的思路比我的element based的写法是要难的; 你画了trace之后就知道, 他实际上最后还是按照一个选1个2, 选2个2...的写法来走的; 而且因为维护了order, 所以最后也完成了去重;
这里有一个陷阱, 你可能会想, 诶, 选0个2的情况怎么办? 实际上, 如果是size based的写法, 是不用考虑0个的情况的; 比如上面的例子找4, 对于1,3这个结果, 不包含2, 对应的其实就是[1]这个位置选择3而不选择2而已: 没错, 你这时候的目光要放在一个level/size/position上面, 而不是这个element怎么样了; backtracking要想写的准确, 感觉最后重要的还是对于level的定义;
当然, 你自然也能理解为什么size based的写法就需要在recursion里面加一个循环了: 因为你要遍历每一个element, 讨论当前这个level可能的选择哪个element;
我在这个帖子下面的归纳:
First, always have a recursion tree in your mind, and the concept of a level of the tree.
size-based backtracking
In size-based approach, each level of the tree actually corresponds to a position/size of the result combination. For the example of finding 4 in 1,2,2,2,3, the combination 2,2 has 2 at position [1], while 1,3 has 3.
OP's solution is size-based: at each level, we use a loop to find an element to put at this position. This easily explains why we need && cand[i] == cand[i-1]: while we are still in the same for loop, we certainly are still in the same level, i.e. the same position of the result combination. Does picking any of the three 2s matter to put them at position [1]? Certainly not. That's why you have to skip them in the same iteration.
Note that, when we picked candidates[1] = 2 to put at combination[1], next recursion we will actually be able to pick candidates[2] = 2 to put at combination[2] again. Note that this has nothing to do with && cand[i] == cand[i-1]. Draw some trace and you will see that what the algorithm do is picking 1..3 2s out of candidates.
element-based backtracking
My code above is element-based, in that, after sorting, I go from small to bigger, and decide how many copies of each element I decide to include in the result combination. In this approach, each level corresponds to a particular (distinct) element! This ensures that no duplicate combinations: each element is uniquely determined at a given level, and will never be revisited again in further down levels.
If you understand this, the code above should be quite self-explanatory. Note that there is a slight difference between the two approaches: I have to consider picking 0 copy of 2 in element-based approach, which is not necessary in the size-based approach. Back again to the example of 1,3 and 2,2, with the former having 0 copies of 2. This does not need to be handled in the size-based approach because, well, it is handled automatically by picking a larger element at combination[1].
还是上一题的时候就贴过一次的, 三个combination sum问题的合集:
@issac3 said in Combination Sum I, II and III Java solution (see the similarities yourself):
Combination Sum I
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(candidates);
backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {
if (remain < 0) return;
else if (remain == 0) list.add(new ArrayList<>(tempList));
else{
for (int i = start; i < cand.length; i++) {
tempList.add(cand[i]);
backtrack(list, tempList, cand, remain-cand[i], i);
tempList.remove(tempList.size()-1);
}
}
}
Combination Sum II
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> list = new LinkedList<List<Integer>>();
Arrays.sort(candidates);
backtrack(list, new ArrayList<Integer>(), candidates, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int[] cand, int remain, int start) {
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for (int i = start; i < cand.length; i++) {
if(i > start && cand[i] == cand[i-1]) continue; // skip duplicates
tempList.add(cand[i]);
backtrack(list, tempList, cand, remain - cand[i], i+1);
tempList.remove(tempList.size() - 1);
}
}
}
Combination Sum III
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<Integer>(), k, n, 1);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int remain, int start) {
if(tempList.size() > k) return;
else if(tempList.size() == k && remain == 0) list.add(new ArrayList<>(tempList));
else{
for (int i = start; i <= 9; i++) {
tempList.add(i);
backtrack(list, tempList, k, remain-i, i+1);
tempList.remove(tempList.size() - 1);
}
}
}
@wfxr said in C++ backtracking solution with detailed explanation:
vector<vector<int>> combinationSum2(vector<int>& A, int target) {
vector<vector<int>> res;
vector<int> path;
sort(A.begin(), A.end());
combinationSum2(A, 0, path, target, res);
return res;
}
void combinationSum2(vector<int>& A, int pos, vector<int> &path, int target, vector<vector<int>> &res) {
if (target == 0) {
res.push_back(path);
return;
}
if (pos == A.size() || target - A[pos] < 0) return;
auto num = A[pos++];
path.push_back(num);
combinationSum2(A, pos, path, target - num, res);
path.pop_back();
while (A[pos] == num) ++pos;
combinationSum2(A, pos, path, target, res);
}
这个方法其实就跟我的思路比较相似了, 是一个element based; 但是他不是跟我一样, 把一个distinct number的处理局限在一个level里面, 而是然其继续向下走, 自然处理;
我感觉我的办法比他的稍微要快一些, 因为他这个做法, 比如对于1,2,2,2,3这个例子, 他需要在每一个2的位置都要完成一次skip duplicate的操作;
注意一个问题, 我一开始认为他这里最后可能有duplicate, 因为比如这三个2, 他都会最后在iteration结尾直接调到3的位置, 但是注意, 这个不是duplicate, 因为这个时候path里面的内容是不同的了;
submission最优解: 17(88):
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> ret = new ArrayList<>();
List<Integer> sol = new ArrayList<>();
helper(candidates, 0, target, sol, ret);
return ret;
}
private void helper(int[] candidates, int idx, int target, List<Integer> sol, List<List<Integer>> ret) {
if (target == 0) {
ret.add(new ArrayList<>(sol));
return;
} else if (target > 0) {
for(int i = idx; i<candidates.length; ++i) {
if (candidates[i] > target) {
break;
}
if (i>idx && candidates[i-1] == candidates[i]) {
continue;
}
sol.add(candidates[i]);
helper(candidates, i+1, target - candidates[i], sol, ret);
sol.remove(sol.size()-1);
}
}
}
}
就是基本的size based的写法; 看来是比我的方法要快一些;
Problem Description
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]
Difficulty:Medium
Total Accepted:141.9K
Total Submissions:400.4K
Contributor:LeetCode
Companies
snapchat
Related Topics
arraybacktracking
Similar Questions
Combination Sum