Combination Sum

Question (LC.39)

Given an array of candidate numbers and a target, find all unique combinations from the candidate array that sum to the target.

Example

Input: candidates = [2, 3, 6, 7], target = 7
Output: [ [2, 2, 3], [7] ]

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);
}

Combination Sums II (LC.40)

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

Analysis

dup doesn't change much right?

Consider this case

I: [10,1,2,7,6,1,5], 8
O: [[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]
EO: [[1,1,6],[1,2,5],[1,7],[2,6]]

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.

Combination Sum III (LC.216)

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;
}

Combination Sum IV (LC.377)

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.

Example

I: nums = [1, 2, 3], target = 4
O: 7 because
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Analysis

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,...].

Reference

Combination Sum IV by Grand Yang