CombinationSum [source code]
public class CombinationSum {
static
/******************************************************************************/
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort (candidates);
List<List<Integer>> res_ls = new LinkedList<> ();
search (candidates, target, 0, 0, res_ls, new LinkedList<> ());
return res_ls;
}
void search (int[] candidates, int target, int idx, int sum, List<List<Integer>> res_ls, LinkedList<Integer> accum) {
if (sum == target) {
res_ls.add (new LinkedList<> (accum));
return;
}
if (idx >= candidates.length) // critical position: has to be after sum==target
return;
if (sum > target)
return;
int cur = candidates[idx];
int num = (target - sum) / cur;
for (int i = 0; i <= num; i++) { // careful with i==0
if (i > 0)
accum.push (cur);
search (candidates, target, idx + 1, sum + i * cur, res_ls, accum);
}
for (int i = 0; i < num; i++)
accum.pop ();
}
}
/******************************************************************************/
public static void main(String[] args) {
CombinationSum.Solution tester = new CombinationSum.Solution();
}
}
每一个数字可以被取无限次, 感觉是一个梗, 后面估计有坑;
另外, 一个明显的backtrack题, 后面pruning肯定又是一个兵家必争之地;
另外, 感觉好像这题用mutating recursion不如用returned recursion好写? 不过我好久没有写mutation recursion了, 担心有点手生;
另外, 既然是搜索, 同样有一个pre leaf还是leaf的位置判断的纠结; base case反正本身也不好写, 先不写; 先写核心逻辑;
pass in argumetns of pre-iteration state
在写DFS类的search当中, 为了避免在最后的leaf位置的处理不精确, 一个重要的概念就是对于一个iteration的定义要清楚, 尤其是你传进去的参数跟这个iteration本身到底是什么关系? 这个以前总结过, 最好的定义, 其实就是你给的参数应该是这个iteration之前的值. 反正关键点就是要consistent就行了;
最后速度是27ms (19%), 不是很理想, 毕竟按理说这类题目我应该很熟悉了; 而且花的时间也不少, 20分钟才AC; 很丢人;
order of base cases
注意代码里面comment出来的两个位置, 比较容易出错的点; 尤其是第一个, 就看出来其实leaf位置判断真的是容易出问题: 尤其是recursion的时候, 好几个base case之间的顺序, 并不是随手写写就行了, 很多时候甚至不画trace都不知道到底应该用什么顺序;
另外, 这个题, 想到sort应该是不难的; array题目本来sort就能降低难度的, 加上这个算法肯定是一个指数级别的函数了, 不sort白不sort;
没有editorial;
discussion一个总结的帖子, 我只贴了这题的了, 其他题目的太多了, 懒得看了; 反正就是提供了一个backtrack的模板的意思:
@issac3 said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
Combination Sum : https://leetcode.com/problems/combination-sum/
public List<List<Integer>> combinationSum(int[] nums, int target) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, target, 0);
return list;
}
private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
if(remain < 0) return;
else if(remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
tempList.remove(tempList.size() - 1);
}
}
}
这个确实写的比我的简练好看; 看到这个算法, 虽然我也很熟悉了, 但是想到一个问题解决之前的base case order的问题; 其实也不是说解决了, 就是适当缓解: 我们可以把一部分的base case放到pre leaf的位置来判断, 比如他这里的index就是; 然后其他的通过真正的base case来判断; 这样可以适当的缓解一些order分布的方式, 不要太死脑筋;
@hide said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
I don't think sorting the nums array is useful in your Combination Sum solution. Your for loop condition should also contain '&& nums[i] <= remain'
想想好像是这样的; 不对, sort虽然不是必须的, 但是是有利的:
@congchengchina said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
@hide you are right, you can safely do it without sorting the array first. But, actually, you can take advantege of sorted array.
Whenever you find remain < 0, it suggests that nums[i] is too large, and it also means the same thing for nums[j] while j is a valid index and j > i in sorted array, so the solution below can be a choice if you sort the array first:
上面那个说不sort的人后来又改口了:
@hide said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
@HaitaoSun Say remain is 7, and you have numbers 8,9,10,11,12,13,14,15,16....... up to a huge number.
If you put the condition in the for loop, it'll break out as soon as you see '8'. In OP's case, it'll check through all the numbers even when it could have just stopped after 8.
So actually, sorting the numbers CAN be useful, if you add the condition I stated to the for loop. Otherwise, sorting the numbers is useless because you aren't using the fact that they're sorted to prune your possible results.
复杂度:
@ranhar said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
@poojasunder27 I think it`s, O(k * 2 ^ n), where k is the average length of all the combinations and n is the size of nums
binary selection思路, 不复杂;
把OP一开始的所有关联题的思路也全都贴出来, 防止以后懒得跑回来这题来看:
@issac3 said in A general approach to backtracking questions in Java (Subsets, Permutations, Combination Sum, Palindrome Partitioning):
This structure might apply to many other backtracking questions, but here I am just going to demonstrate Subsets, Permutations, and Combination Sum.
Subsets : [https://leetcode.com/problems/subsets/][1]
public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){ list.add(new ArrayList<>(tempList)); for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } }Subsets II (contains duplicates) : [https://leetcode.com/problems/subsets-ii/][2]
public List<List<Integer>> subsetsWithDup(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){ list.add(new ArrayList<>(tempList)); for(int i = start; i < nums.length; i++){ if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates tempList.add(nums[i]); backtrack(list, tempList, nums, i + 1); tempList.remove(tempList.size() - 1); } }
Permutations : [https://leetcode.com/problems/permutations/][3]
public List<List<Integer>> permute(int[] nums) { List<List<Integer>> list = new ArrayList<>(); // Arrays.sort(nums); // not necessary backtrack(list, new ArrayList<>(), nums); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){ if(tempList.size() == nums.length){ list.add(new ArrayList<>(tempList)); } else{ for(int i = 0; i < nums.length; i++){ if(tempList.contains(nums[i])) continue; // element already exists, skip tempList.add(nums[i]); backtrack(list, tempList, nums); tempList.remove(tempList.size() - 1); } } }Permutations II (contains duplicates) : [https://leetcode.com/problems/permutations-ii/][4]
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){ if(tempList.size() == nums.length){ list.add(new ArrayList<>(tempList)); } else{ for(int i = 0; i < nums.length; i++){ if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue; used[i] = true; tempList.add(nums[i]); backtrack(list, tempList, nums, used); used[i] = false; tempList.remove(tempList.size() - 1); } } }
Combination Sum : [https://leetcode.com/problems/combination-sum/][5]
public List<List<Integer>> combinationSum(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, target, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < nums.length; i++){ tempList.add(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements tempList.remove(tempList.size() - 1); } } }Combination Sum II (can't reuse same element) : [https://leetcode.com/problems/combination-sum-ii/][6]
public List<List<Integer>> combinationSum2(int[] nums, int target) { List<List<Integer>> list = new ArrayList<>(); Arrays.sort(nums); backtrack(list, new ArrayList<>(), nums, target, 0); return list; } private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){ if(remain < 0) return; else if(remain == 0) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < nums.length; i++){ if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates tempList.add(nums[i]); backtrack(list, tempList, nums, remain - nums[i], i + 1); tempList.remove(tempList.size() - 1); } } }Palindrome Partitioning : [https://leetcode.com/problems/palindrome-partitioning/][7]
public List<List<String>> partition(String s) { List<List<String>> list = new ArrayList<>(); backtrack(list, new ArrayList<>(), s, 0); return list; } public void backtrack(List<List<String>> list, List<String> tempList, String s, int start){ if(start == s.length()) list.add(new ArrayList<>(tempList)); else{ for(int i = start; i < s.length(); i++){ if(isPalindrome(s, start, i)){ tempList.add(s.substring(start, i + 1)); backtrack(list, tempList, s, i + 1); tempList.remove(tempList.size() - 1); } } } } public boolean isPalindrome(String s, int low, int high){ while(low < high) if(s.charAt(low++) != s.charAt(high--)) return false; return true; }[1]: https://leetcode.com/problems/subsets/
[2]: https://leetcode.com/problems/subsets-ii/
[3]: https://leetcode.com/problems/permutations/
[4]: https://leetcode.com/problems/permutations-ii/
[5]: https://leetcode.com/problems/combination-sum/
@prime_tang said in Accepted 16ms c++ solution use backtracking, easy understand.:
Accepted 16ms c++ solution use backtracking for [Combination Sum][1]:
class Solution {
public:
std::vector<std::vector<int> > combinationSum(std::vector<int> &candidates, int target) {
std::sort(candidates.begin(), candidates.end());
std::vector<std::vector<int> > res;
std::vector<int> combination;
combinationSum(candidates, target, res, combination, 0);
return res;
}
private:
void combinationSum(std::vector<int> &candidates, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin) {
if (!target) {
res.push_back(combination);
return;
}
for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i) {
combination.push_back(candidates[i]);
combinationSum(candidates, target - candidates[i], res, combination, i);
combination.pop_back();
}
}
};
跟之前那个思路是差不多的, 不过他多放了一个(sum < target)的判断到pre leaf的位置;
Accepted 12ms c++ solution use backtracking for [Combination Sum II][2]:
class Solution {
public:
std::vector<std::vector<int> > combinationSum2(std::vector<int> &candidates, int target) {
std::sort(candidates.begin(), candidates.end());
std::vector<std::vector<int> > res;
std::vector<int> combination;
combinationSum2(candidates, target, res, combination, 0);
return res;
}
private:
void combinationSum2(std::vector<int> &candidates, int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin) {
if (!target) {
res.push_back(combination);
return;
}
for (int i = begin; i != candidates.size() && target >= candidates[i]; ++i)
if (i == begin || candidates[i] != candidates[i - 1]) {
combination.push_back(candidates[i]);
combinationSum2(candidates, target - candidates[i], res, combination, i + 1);
combination.pop_back();
}
}
};
Accepted 0ms c++ solution use backtracking for [Combination Sum III][3]:
class Solution {
public:
std::vector<std::vector<int> > combinationSum3(int k, int n) {
std::vector<std::vector<int> > res;
std::vector<int> combination;
combinationSum3(n, res, combination, 1, k);
return res;
}
private:
void combinationSum3(int target, std::vector<std::vector<int> > &res, std::vector<int> &combination, int begin, int need) {
if (!target) {
res.push_back(combination);
return;
}
else if (!need)
return;
for (int i = begin; i != 10 && target >= i * need + need * (need - 1) / 2; ++i) {
combination.push_back(i);
combinationSum3(target - i, res, combination, i + 1, need - 1);
combination.pop_back();
}
}
};
[1]: https://leetcode.com/problems/combination-sum/
后面两题因为没有做, 就没有看了;
@mycoy said in Accepted 16ms c++ solution use backtracking, easy understand.:
I think the runtime should be O(2^n)
T(n) = T(n-1) + T(n-2) + T(n-2) ...
T(n-1) = T(n-2)+T(n-3)... use this to replace T(n-1) in the above,
so T(n) = 2 * [ T(n-2) + T(n-3) ], and so on, T(n) = O(2^n)
结论是对的, 不过思路有点复杂;
想了想, 不对啊, 这题这个是binary的吗? 这里因为可以reuse, 所以一个数字最后的selection的可能性其实是不止2的; 比如target如果比所有的nums都大很多, 那么最后的结果最起码是跟2^N的差别应该很大的;
他上面的这个分析的问题就在于, 每一个类似T(N-1)的子项, 是还有一个系数的; 如果target是10000, nums[0]是1, 那么这个系数实际上可以非常的大;
底下貌似有人也是赞同我这个观点的;
@shpolsky said in Iterative Java DP solution:
Hi guys!
The main idea reminds an approach for solving coins/knapsack problem - to store the result for all i < target and create the solution from them. For that for each t from 1 to our target we try every candidate which is less or equal to t in ascending order. For each candidate "c" we run through all combinations for target t-c starting with the value greater or equal than c to avoid duplicates and store only ordered combinations.
public class Solution {
public List<List<Integer>> combinationSum(int[] cands, int t) {
Arrays.sort(cands); // sort candidates to try them in asc order
List<List<List<Integer>>> dp = new ArrayList<>();
for (int i = 1; i <= t; i++) { // run through all targets from 1 to t
List<List<Integer>> newList = new ArrayList(); // combs for curr i
// run through all candidates <= i
for (int j = 0; j < cands.length && cands[j] <= i; j++) {
// special case when curr target is equal to curr candidate
if (i == cands[j]) newList.add(Arrays.asList(cands[j]));
// if current candidate is less than the target use prev results
else for (List<Integer> l : dp.get(i-cands[j]-1)) {
if (cands[j] <= l.get(0)) {
List cl = new ArrayList<>();
cl.add(cands[j]); cl.addAll(l);
newList.add(cl);
}
}
}
dp.add(newList);
}
return dp.get(t-1);
}
}
Hope it helps!
DP算法的核心还是这个build up的过程;
思路本身其实很优秀, 就是不知道复杂度多少; 注意他这里的一个操作:
List cl = new ArrayList<>();
cl.add(cands[j]); cl.addAll(l);
用这个来避免后面add at 0这个带来的代价; 这个人写代码可以说是非常细心了;
@stonepeter said in Iterative Java DP solution:
@coolth check " if (cands[j] <= l.get(0)) " to remove dulplicate.
对应的就是:
starting with the value greater or equal than c to avoid duplicates and store only ordered combinations.
能够想到这样维护一个invariant来避免duplicate还是挺不简单的; 本身的想法肯定还是一个enforce order, 但是实际的实现并没有那么trivial;
你能够想到这个算法的复杂度吗? 实际上, 还是指数级别, 因为你要遍历之前的t的所有的结果, 所以这个最后还是一个tree一样的结构;
不过最后好像都反映这个算法其实比普通的backtracking要慢;
但是这里这个tree的height好像实际上应该是跟target挂钩, 而之前的backtracking的做法, height应该是跟N挂钩; 具体两者之间最后的结果是什么关系, 还不太好说;
submission最优解: 16(93):
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
final List<List<Integer>> ans = new ArrayList<>();
search(candidates, 0, target, new Integer[target], 0, ans);
return ans;
}
private void search(int[] candidates, int st,
int target,
Integer[] paper, int len,
List<List<Integer>> ans) {
if (target == 0) {
final Integer[] temp = new Integer[len];
System.arraycopy(paper, 0, temp, 0, len);
ans.add(Arrays.asList(temp));
return;
}
for(int i=st; i<candidates.length; i++) {
if (i>st && candidates[i] == candidates[i-1]) continue;
if (target < candidates[i]) break;
paper[len] = candidates[i];
search(candidates, i, target-candidates[i], paper, len+1, ans);
}
}
}
好像就是用array来避免用collection做accum而已, 应该是没有什么其他的名堂了; 另外, 他这个算法好像还故意handle了duplicate;
Problem Description
Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
- All numbers (including target) will be positive integers.
- The solution set must not contain duplicate combinations.
For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:
[
[7],
[2, 2, 3]
]
Difficulty:Medium
Total Accepted:201.9K
Total Submissions:495.8K
Contributor:LeetCode
Companies
ubersnapchat
Related Topics
arraybacktracking
Similar Questions
Letter Combinations of a Phone NumberCombination Sum IICombinationsCombination Sum IIIFactor CombinationsCombination Sum IV