A candidate can be used unlimited number of times.
Analysis
Be careful with the input, it might contain duplicates.
Step 1 Remove duplicates
Step 2 Define DFS(parameter/return value, recursive calls, stop condition)
Step 3 Write DFS
Code
Main function
/*
How is this different from subsets?
1. dup
2. use each number unlimited number of times
3. stop at a target
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> results = new ArrayList<>();
if (candidates == null || candidates.length == 0) {
return results;
}
Arrays.sort(candidates);
combDFS(results, candidates, target, 0, new ArrayList<Integer>());
return results;
}
DFS Search
private void combDFS( List<List<Integer>> results, int[] candidates,
int target, int startIndex, List<Integer> combination) {
// stop conditions
if (target < 0) {
return;
}
if (target == 0) {
results.add(new ArrayList<>(combination));
return;
}
// dfs
for (int i = startIndex; i < candidates.length; i++) {
combination.add(candidates[i]);
combDFS(results, candidates, target - candidates[i], i, combination);
combination.remove(combination.size() - 1);
}
}
We can improve a bit on the stopping conditions. We don't have to go down one more level until the target becomes negative. We can simply skip the candidates in the for loop that is bigger than the current target.
// dfs
for (int i = startIndex; i < candidates.length; i++) {
if (target < candidates[i]) {
break;
}
combination.add(candidates[i]);
combDFS(results, candidates, target - candidates[i], i, combination);
combination.remove(combination.size() - 1);
}
each candidate can only be used once
candidate list may contain duplicates
Approach
exhaustive search of course
Step 1 define recursion
sumHelp() will find all possible combinations with candidates[i:n] and the remaining target
Step 2 recursive calls
for each candidate
sumHelper(i+1, target - candidate)
Step 3 stop conditions
if (target == 0)
add combination to result
if (target < 0)
return
We want to keep [1,1,6] but get rid of [1,2,5], [1,7]. Essentially, we want to avoid using the second 1 as the root of the search. One may attempt if (i != 0 && candidates[i] == candidates[i-1]) continue;. But it gets rid of [1,1,6] as well. We want to only avoid duplicates on the same level so i != startIndex.
Code
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> result = new ArrayList<>();
List<Integer> combination = new ArrayList<>();
sumHelper(result, combination, candidates, target, 0);
return result;
}
private void sumHelper(List<List<Integer>> result,
List<Integer> combination,
int[] candidates,
int target,
int startIndex) {
// stop condition
if (target == 0) {
result.add(new ArrayList<>(combination));
return;
}
if (target < 0) {
return;
}
// recursive calls
for (int i = startIndex; i < candidates.length; i++) {
// since canidates are sorted we can prune the search
// if (candidates[i] > target) {
// break;
// }
// avoid searching the same subtree again
// can[i] == can[i-1] can be child and parent
// but i != startIndex ensures that they are siblings
if (i != startIndex && candidates[i] == candidates[i-1]) {
continue;
}
combination.add(candidates[i]);
sumHelper(result, combination, candidates, target - candidates[i], i + 1);
combination.remove(combination.size() - 1);
}
}
The smart pruning will improve performance by a lot. It will bring the runtime from 21% to 93% on LC.
Find all possible combinations of k numbers that add up to a target. Only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Example
Always run examples FIRST. Running examples can give you another chance and read and understand the question better. It can also clarify the edge cases.
I: k = 3, target = 7
O: [[1,2,4]]
I: k = 3, target = 9
O: [[1,2,6], [1,3,5], [2,3,4]]
Analysis
We want to find all combinations 9 choose k, such that the combSum == target.
Approach
1. parameter
(k, target, results, startNum, combination, combSum)
we can do k-1 or just use combination.size()
combSum is not necessary since we can do target - num
2. dfs
for num from startNum to n
previsit: combination.add(num), combSum[0] += num
dfs
postvisit: combination.remove(num), combSum[0] -= num
end for
3. stop condition (brute force then optimize)
if (k == 0)
check combSum == target
Code
private static final int N = 9;
public List<List<Integer>> combinationSum3(int k, int target) {
List<List<Integer>> results = new ArrayList<>();
if (k > N) {
return results;
}
combineDFS(k, target, results, 1, new ArrayList<>(), new int[] {0});
return results;
}
private void combineDFS(int k, int target, List<List<Integer>> results,
int startNum, List<Integer> combination, int[] combSum) {
// stop condition
if (combination.size() == k) {
if (combSum[0] == target) {
results.add(new ArrayList<>(combination));
}
return;
}
// dfs
for (int num = startNum; num <= N; num++) {
combination.add(num);
combSum[0] += num;
combineDFS(k, target, results, num + 1, combination, combSum);
combination.remove(combination.size() - 1);
combSum[0] -= num;
}
}
Optimization
Adding this simple if statement will boost the performance from 12 to 58 percentile.
if (combSum[0] > target) {
return;
}
We can also do the pruning inside the for loop (save one level/stack frame more efficient)
if (combSum[0] + num > target) {
break;
}
Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.
I originally thought this is combination with repetition. But the example shows [1,1,2], [1,2,1], and [2,1,1] are three different "combinations". In fact, under this definition, there's an infinite number of "combinations". For example, given a set [1,2,3], we can have {[1-3],[1-3],[1-3],[1-3], ...} so 3x3x3x3x3... number of combinations.
Brute Force Approach
find all combinations (where sum < target)
add it to results if combSum == target
- parameter
(nums, target)
don't need startIndex, always start from index 0
- dfs
for i from o to n-1
dfs(nums, target - nums[i])
end for
- stop condition
if (target < 0)
return;
if (target == 0)
results++;
return;
Code
private int results = 0;
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return results;
}
combineDFS(nums, target);
return results;
}
private void combineDFS(int[] nums, int target) {
// stop conditions
if (target < 0) {
return;
}
if (target == 0) {
results++;
return;
}
// dfs
for (int i = 0; i < nums.length; i++) {
combineDFS(nums, target - nums[i]);
}
}
But Time Limit Exceeded ٩ʕ•͡וʔ۶
Last executed input:
Expected answer: 181997601
Analysis 2
Draw the recursion tree and we can observe starting from [2] has overlapping subproblems as starting from [1].
DFS(nums, 4)
DFS(nums, 3)
DFS(nums, 2)
DFS(nums, 1)
DFS(nums, 0)
end
end
DFS(nums, 0)
end
DFS(nums, 2) // what if we can memoize this
DP Approach
In addition to the overlapping subproblems, the question is only asking for returning a count instead of a collection of all combinations. Also, it is unreasonable to search for all 181997601 combinations.
DP Solution
1. define subproblem
DFS[i] is the number of combinations we have for target i
2. write recurrence
solve by prefix
DFS[n] += DFS[n - nums[x]] for x from 0 to nums.length-1
3. topo order
for n from 1 to target
4. base case
DP[negative targets] = 0
DP[0] = 1
5. return result
DFS[target]
Top-Down (Memoization)
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[target + 1];
return combineDFS(nums, target, dp);
}
private int combineDFS(int[] nums, int target, int[] dp) {
// stop conditions
// move this inside for loop
if (target < 0) {
return 0;
}
// init base case for dp
if (target == 0) {
return 1;
}
// what if there are targets that we have actually 0 combinations
if (dp[target] != 0) {
return dp[target];
}
// dfs
for (int i = 0; i < nums.length; i++) {
dp[target] += combineDFS(nums, target - nums[i], dp);
}
// return value
return dp[target];
}
Now we can handle [1,2,3], 32 case. But [3,33,333], 10000 makes the program TLE again.
Updated Version (See comments above)
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
int[] dp = new int[target + 1];
Arrays.fill(dp, -1);
dp[0] = 1;
Arrays.sort(nums); // so we can break instead of continue
return combineDFS(nums, target, dp);
}
private int combineDFS(int[] nums, int target, int[] dp) {
// memoization
if (dp[target] != -1) {
return dp[target];
}
// dfs since we label unvisitd as -1
// we need to have a count that starts from 0
int count = 0;
for (int i = 0; i < nums.length; i++) {
int nextTarget = target - nums[i];
if (nextTarget < 0) {
break;
}
count += combineDFS(nums, nextTarget, dp);
}
// return value
dp[target] = count;
return dp[target];
}
Bottom-Up (Tabulation)
Simplicity is harder to achieve than complexity.
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// init base case
dp[0] = 1;
Arrays.sort(nums); // so we can break instead of continue
// topo order
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (i - num < 0) {
break;
}
dp[i] += dp[i - num];
}
}
// return result
return dp[target];
}
Follow Up
What if negative numbers are allowed in the given array?
Then we need to add an extra constraint on the max length of a combination. Otherwise, we can run into the an infinite long combination such as [...,-1,-1,-1,1,1,1,...].
