Skip to content

Instantly share code, notes, and snippets.

@daifu
Last active April 24, 2018 12:47
Show Gist options
  • Save daifu/5844049 to your computer and use it in GitHub Desktop.
Save daifu/5844049 to your computer and use it in GitHub Desktop.
Combination Sum - Leetcode
/*
Given a set of candidate numbers (C) 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.
Elements in a combination (a1, a2, ..., ak) must be in non-descending order. (ie, a1 ? a2 ? ... ? ak).
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]
Algorithm:
Basically find out the combination of the int array to sum up to the target and
it needs to take care of the repeated number, such as [2,2,3] and [1,6] for 7
This algorithm has time complexity O((n+k)!) where n is the size of candidates,
and k is the max repeated times for each candidates
and space complexity O(m) where m is the size of array for the solution.
*/
public class Solution {
public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> list = new ArrayList<Integer>();
if(candidates.length == 0) return ret;
Arrays.sort(candidates);
combinationSumHelper(candidates, target, 0, 0, ret, list);
return ret;
}
public void combinationSumHelper(int[] input, int target, int start, int sum,
ArrayList<ArrayList<Integer>> ret,
ArrayList<Integer> list) {
if(sum > target) return;// Note: This method cannot finish large set if this line is missing
for(int i = start; i < input.length; i++) {
list.add(input[i]);
sum += input[i];
if(sum == target) {
ret.add(new ArrayList<Integer>(list));
sum -= list.get(list.size() - 1);
list.remove(list.size() - 1);
return;
}
if(sum < target) {
combinationSumHelper(input, target, i, sum, ret, list);
} else {
combinationSumHelper(input, target, i+1, sum, ret, list);
}
sum -= list.get(list.size() - 1);
list.remove(list.size() - 1);
}
return;
}
}
@Buzz-Lightyear
Copy link

What's the point of else { combinationSumHelper(input, target, i+1, sum, ret, list); }? Won't it return immediately as sum exceeds target?

@Buzz-Lightyear
Copy link

Great solution, removed redundancy from your code - https://gist.github.com/Buzz-Lightyear/85aab6e372423d025e91

@aoben10
Copy link

aoben10 commented Jun 14, 2016

Why do we use depth first search here? As in when I read this problem, how would i know DFS is the way to approach it?

@snehilbhatt
Copy link

@aoben10 : Here we need all the combinations that result in the target. Another approach would have been using Dynamic Programming if we were asked for say the best result. Using DFS, we are making sure of scanning every element. Note repetitions are allowed, so we are scanning every candidate element again and again until the sum exceeds the target.

@kunalrustagi08
Copy link

What if repetitions are not allowed? Is there any way to limit the number of elements required for the combinational sum?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment