Related: LeetCode 39 - Combination Sum
Leetcode 216 Combination Sum III
LeetCode 377 - Combination Sum IV
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.
Leetcode 216 Combination Sum III
LeetCode 377 - Combination Sum IV
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.
- All numbers (including target) will be positive integers.
- Elements in a combination
(a1,a2,…,ak) must be in non-descending order. (i.e.,a1≤a2≤⋯≤ak ). - The solution set must not contain duplicate combinations.
Almost the same as last problem LeetCode 39 - Combination Sum
Difference:
1. Element can only be used once and may have duplicated elements.
Tips:
1. The index for next level will be current index+1;
2. To avoid duplicated results: make sure if the iteration pointer i is not the start index, it will skip the duplicated element. Note: always execute the first loop(i==start).
eg. 2,2,2,3 target =7, the recursion tree will look like this:
2,2,2,3--> 2,2,3 --> 2,3, Notice: during the recursion, we skipped several 2,2,3 and 2,3
1. Element can only be used once and may have duplicated elements.
Tips:
1. The index for next level will be current index+1;
2. To avoid duplicated results: make sure if the iteration pointer i is not the start index, it will skip the duplicated element. Note: always execute the first loop(i==start).
eg. 2,2,2,3 target =7, the recursion tree will look like this:
2,2,2,3--> 2,2,3 --> 2,3, Notice: during the recursion, we skipped several 2,2,3 and 2,3
https://discuss.leetcode.com/topic/44037/combination-sum-i-ii-and-iii-java-solution-see-the-similarities-yourself/
https://discuss.leetcode.com/topic/19845/java-solution-using-dfs-easy-understand
http://codeganker.blogspot.com/2014/03/combination-sum-ii-leetcode.html
在这里我们还是需要在每一次for循环前做一次判断,因为虽然一个元素不可以重复使用,但是如果这个元素重复出现是允许的,但是为了避免出现重复的结果集,我们只对于第一次得到这个数进行递归,接下来就跳过这个元素了,因为接下来的情况会在上一层的递归函数被考虑到,这样就可以避免重复元素的出现
http://noalgo.info/935.html
由于可能出现相同元素,先排序方便后续处理。dfs时每次处理一个数字,相同的数字一起处理,相同数字可以不选,也可以每次选择一个,但不能选择超过其出现次数的个数。
http://www.jiuzhang.com/solutions/combination-sum-ii/
https://discuss.leetcode.com/topic/5777/dp-solution-in-python
X. Iterative - DFS
http://siyang2leetcode.blogspot.com/2015/03/combination-sum-ii.html
http://siyang2leetcode.blogspot.com/2015/03/combination-sum-ii.html
If I directly use List<Integer> as nodes, I need to find a way to store the sum of the list and the current index. I could use the first element to store the sum, the second element to store the current index.
http://www.programmeronrails.com/2015/11/14/coding-problem-combination-sum-ii/
Create two many lists - some lists are invalid and discarded.
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new LinkedList<List<Integer>>();
// sort the candidates
Arrays.sort(candidates);
// collect possible candidates from small to large.
find(new ArrayList<Integer>(), target, candidates, 0, results);
return results;
}
private void find(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> results) {
if (target == 0) {
results.add(list);
return;
}
for (int i=index; i < candidates.length; i++) {
// to avoid duplicate results by skipping the
// candidate with the same value
if(i>index && candidates[i] == candidates[i-1])
continue;
int newTarget = target - candidates[i];
if (newTarget >= 0) {
List<Integer> copy = new ArrayList<Integer>(list);
copy.add(candidates[i]);
// as the candidate could not be selected again,
// the next candidate available is candidates[i+1]
find(copy, newTarget, candidates, i+1, results);
} else {
break;
}
}
}
http://shanjiaxin.blogspot.com/2014/02/combination-sum-ii-leetcode.html
Change target to maintain remaining target.
public static ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
combinationSumHelper(result, list, num, target, 0);
return result;
}
private static void combinationSumHelper(ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> list, int[] num, int target, int position) {
int sum = 0;
for (int x: list) {
sum += x;
}
if (sum == target) {
result.add(new ArrayList<Integer>(list));
return;
}
if (sum < target) {
for (int i = position; i<num.length; i++) {
if ( i != position && num[i] == num[i-1]) {
continue;
}
list.add(num[i]);
combinationSumHelper(result, list, num, target, i+1);
list.remove(list.size() - 1);
}
}
}
http://bangbingsyb.blogspot.com/2014/11/leetcode-combination-sum-i-ii.html
https://discuss.leetcode.com/topic/60535/understanding-the-differences-between-the-dp-solution-and-simple-recursive-which-one-is-really-better
https://discuss.leetcode.com/topic/19845/java-solution-using-dfs-easy-understand
public ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (num == null || num.length == 0)
return result;
Arrays.sort(num); // Sort the candidate in non-descending order
ArrayList<Integer> current = new ArrayList<Integer>();
recursiveAppend(num, target, 0, current, result);
return result;
}
private void recursiveAppend(int[] num, int target, int startIndex, ArrayList<Integer> current,
ArrayList<ArrayList<Integer>> result) {
if (target < 0)
return;
if (target == 0) { // The current array is an solution
result.add(new ArrayList<Integer>(current));
return;
}
for (int i = startIndex; i < num.length; i++) {
if (num[i] > target) // No need to try the remaining candidates
break;
if (i > startIndex && num[i] == num[i-1])//\\
// The same number has been added earlier within the loop
continue;
// Add candidate[i] to the current array
current.add(num[i]);
// Recursively append the current array to compose a solution
recursiveAppend(num, target-num[i], i+1, current, result);
// Remove candidate[i] from the current array, and try next candidate in the next loop
current.remove(current.size()-1);
}
}
https://discuss.leetcode.com/topic/44037/combination-sum-i-ii-and-iii-java-solution-see-the-similarities-yourselfpublic 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; /** no solution */
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);
}
}
}
https://discuss.leetcode.com/topic/34364/java-solutions-beats-99-87 public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> results = new ArrayList<>();
calcCombinationSum2(candidates, 0, new int[candidates.length], 0, target, results);
return results;
}
private void calcCombinationSum2(int[] candidates, int cindex, int[] list, int lindex, int target, List<List<Integer>> results) {
if (target == 0) {
List<Integer> result = new ArrayList<>();
for (int i = 0; i < lindex; i++) {
result.add(list[i]);
}
results.add(result);
return;
}
int prev = 0;
for (int i = cindex; i < candidates.length; i++) {
if (candidates[i] != prev) {
if (target - candidates[i] < 0) {
break;
}
list[lindex] = candidates[i];
calcCombinationSum2(candidates, i + 1, list, lindex + 1, target - candidates[i], results);
prev = candidates[i];
}
}
}
http://codeganker.blogspot.com/2014/03/combination-sum-ii-leetcode.html
在这里我们还是需要在每一次for循环前做一次判断,因为虽然一个元素不可以重复使用,但是如果这个元素重复出现是允许的,但是为了避免出现重复的结果集,我们只对于第一次得到这个数进行递归,接下来就跳过这个元素了,因为接下来的情况会在上一层的递归函数被考虑到,这样就可以避免重复元素的出现
http://noalgo.info/935.html
由于可能出现相同元素,先排序方便后续处理。dfs时每次处理一个数字,相同的数字一起处理,相同数字可以不选,也可以每次选择一个,但不能选择超过其出现次数的个数。
http://www.jiuzhang.com/solutions/combination-sum-ii/
private ArrayList<ArrayList<Integer>> results; public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) { if (candidates.length < 1) { return results; } ArrayList<Integer> path = new ArrayList<Integer>(); java.util.Arrays.sort(candidates); results = new ArrayList<ArrayList<Integer>> (); combinationSumHelper(path, candidates, target, 0); return results; } private void combinationSumHelper(ArrayList<Integer> path, int[] candidates, int sum, int pos) { if (sum == 0) { results.add(new ArrayList<Integer>(path)); } if (pos >= candidates.length || sum < 0) { return; } int prev = -1; for (int i = pos; i < candidates.length; i++) { if (candidates[i] != prev) { path.add(candidates[i]); combinationSumHelper(path, candidates, sum - candidates[i], i + 1); prev = candidates[i]; path.remove(path.size()-1); } } }X. DP
https://discuss.leetcode.com/topic/5777/dp-solution-in-python
I also did it with recursion, turns out the DP solution is 3~4 times faster.
def combinationSum2(self, candidates, target):
candidates.sort()
table = [None] + [set() for i in range(target)]
for i in candidates:
if i > target:
break
for j in range(target - i, 0, -1):
table[i + j] |= {elt + (i,) for elt in table[j]}
table[i].add((i,))
return map(list, table[target])
X. Iterative - DFS
http://siyang2leetcode.blogspot.com/2015/03/combination-sum-ii.html
class SumNode{
int index;
int sum;
List<Integer> path;
SumNode(int index, int value, List<Integer> path){
this.index = index;
this.sum = value;
this.path = new ArrayList<Integer>(path);
}
public void addNumber(int value){
this.sum += value;
this.path.add(value);
}
}
public List<List<Integer>> combinationSum2(int[] num, int target) {
List<List<Integer>> rslt = new ArrayList<List<Integer>>();
Set<List<Integer>> set = new HashSet<List<Integer>>();
Stack<SumNode> stack = new Stack<SumNode>();
Arrays.sort(num);
SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());
stack.push(root);
while(!stack.isEmpty()){
SumNode node = stack.pop();
for(int i = node.index+1;i < num.length;i++){
if(node.sum + num[i] > target) break;
SumNode child = new SumNode(i, node.sum, node.path);
child.addNumber(num[i]);
if(child.sum==target) set.add(child.path);
else stack.push(child);
}
}
rslt.addAll(set);
return rslt;
}
X. Iterative Version: BFS Queuehttp://siyang2leetcode.blogspot.com/2015/03/combination-sum-ii.html
public class Solution {
class SumNode{
int index;
int sum;
List<Integer> path;
SumNode(int index, int value, List<Integer> path){
this.index = index;
this.sum = value;
this.path = new ArrayList<Integer>(path);
}
public void addNumber(int value){
this.sum += value;
this.path.add(value);
}
}
public List<List<Integer>> combinationSum2(int[] num, int target) {
List<List<Integer>> rslt = new ArrayList<List<Integer>>();
Set<List<Integer>> set = new HashSet<List<Integer>>();
Queue<SumNode> queue = new LinkedList<SumNode>();
Arrays.sort(num);
SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());
queue.add(root);
while(!queue.isEmpty()){
SumNode node = queue.poll();
for(int i = node.index+1;i < num.length;i++){
if(node.sum + num[i] > target) break;
SumNode child = new SumNode(i, node.sum, node.path);
child.addNumber(num[i]);
if(child.sum==target) set.add(child.path);
else queue.add(child);
}
}
rslt.addAll(set);
return rslt;
}
}
X. DFS Stack
Improved Way: Can I apply iterative method without using extra class (SumNode in the above code). class SumNode{
int index;
int sum;
List<Integer> path;
SumNode(int index, int value, List<Integer> path){
this.index = index;
this.sum = value;
this.path = new ArrayList<Integer>(path);
}
public void addNumber(int value){
this.sum += value;
this.path.add(value);
}
}
public List<List<Integer>> combinationSum2(int[] num, int target) {
List<List<Integer>> rslt = new ArrayList<List<Integer>>();
Set<List<Integer>> set = new HashSet<List<Integer>>();
Stack<SumNode> stack = new Stack<SumNode>();
Arrays.sort(num);
SumNode root = new SumNode(-1, 0, new ArrayList<Integer>());
stack.push(root);
while(!stack.isEmpty()){
SumNode node = stack.pop();
for(int i = node.index+1;i < num.length;i++){
if(node.sum + num[i] > target) break;
SumNode child = new SumNode(i, node.sum, node.path);
child.addNumber(num[i]);
if(child.sum==target) set.add(child.path);
else stack.push(child);
}
}
rslt.addAll(set);
return rslt;
}
If I directly use List<Integer> as nodes, I need to find a way to store the sum of the list and the current index. I could use the first element to store the sum, the second element to store the current index.
public List<List<Integer>> combinationSum2(int[] num, int target) {
List<List<Integer>> rslt = new ArrayList<List<Integer>>();
Set<List<Integer>> set = new HashSet<List<Integer>>();
Stack<List<Integer>> stack = new Stack<List<Integer>>();
Arrays.sort(num);
// initial list
List<Integer> root = new ArrayList<Integer>();
root.add(0);
root.add(-1);
// DFS
stack.push(root);
while(!stack.isEmpty()){
List<Integer> list = stack.pop();
// check if target found
if(list.get(0)==target){
List<Integer> path = new ArrayList<Integer>();
for(int i = 0;i < list.size()-2;i++)
path.add(list.get(i+2));
set.add(path);
}
// push child list
for(int i = list.get(1)+1;i < num.length;i++){
if(list.get(0)+num[i] > target) break;
List<Integer> path = new ArrayList<Integer>(list);
path.set(0, path.get(0)+num[i]);
path.set(1, i);
path.add(num[i]);
stack.push(path);
}
}
rslt.addAll(set);
return rslt;
}
X.http://www.programmeronrails.com/2015/11/14/coding-problem-combination-sum-ii/
Create two many lists - some lists are invalid and discarded.
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> results = new LinkedList<List<Integer>>();
// sort the candidates
Arrays.sort(candidates);
// collect possible candidates from small to large.
find(new ArrayList<Integer>(), target, candidates, 0, results);
return results;
}
private void find(List<Integer> list, int target, int[] candidates, int index, List<List<Integer>> results) {
if (target == 0) {
results.add(list);
return;
}
for (int i=index; i < candidates.length; i++) {
// to avoid duplicate results by skipping the
// candidate with the same value
if(i>index && candidates[i] == candidates[i-1])
continue;
int newTarget = target - candidates[i];
if (newTarget >= 0) {
List<Integer> copy = new ArrayList<Integer>(list);
copy.add(candidates[i]);
// as the candidate could not be selected again,
// the next candidate available is candidates[i+1]
find(copy, newTarget, candidates, i+1, results);
} else {
break;
}
}
}
http://shanjiaxin.blogspot.com/2014/02/combination-sum-ii-leetcode.html
Change target to maintain remaining target.
public static ArrayList<ArrayList<Integer>> combinationSum2(int[] num, int target) {
Arrays.sort(num);
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
combinationSumHelper(result, list, num, target, 0);
return result;
}
private static void combinationSumHelper(ArrayList<ArrayList<Integer>> result,
ArrayList<Integer> list, int[] num, int target, int position) {
int sum = 0;
for (int x: list) {
sum += x;
}
if (sum == target) {
result.add(new ArrayList<Integer>(list));
return;
}
if (sum < target) {
for (int i = position; i<num.length; i++) {
if ( i != position && num[i] == num[i-1]) {
continue;
}
list.add(num[i]);
combinationSumHelper(result, list, num, target, i+1);
list.remove(list.size() - 1);
}
}
}
http://bangbingsyb.blogspot.com/2014/11/leetcode-combination-sum-i-ii.html
https://discuss.leetcode.com/topic/60535/understanding-the-differences-between-the-dp-solution-and-simple-recursive-which-one-is-really-better
DP Solution:
- Start by creating an array of [target+1]. Call it arr.
- Initialize value at arr[candidates[i]] to be a set only containing {candidates[i]}.
- If there are any other indices j of arr that are non-empty, populate the arr[j+candidates[i]] with the set of arr[j] + candidates[i].
Good for:
If target is relatively small, and/or numbers in candidates are very dense.
O(M*N) where M is target, and N is candidates.size()
If target is relatively small, and/or numbers in candidates are very dense.
O(M*N) where M is target, and N is candidates.size()
Recursive Solution:
- Start by recursing with an empty set on every element.
- DFS by adding the ith element on the temporary vector, calling the recursive function with the ith element added, then remove it.
- When the remaining is 0(we subtract target by candidate[i] every recursive call to candidate[i]), we add the result into the vector<vector<int>>.
Good for:
If M is overwhelmingly large.
Read full article from LeetCode - Combination Sum II | Darren's BlogIf M is overwhelmingly large.