Using BackTracking Algorithm to Find the Combination Integer Sum

Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target. The same repeated number may be chosen from candidates unlimited number of times.

Note:
All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:
Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]

Example 2:
Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

This puzzle is very similar to the Coin Change problem except that we need to find out the detailed combination (not just the total number of solutions).

BackTracking Algorithm and Depth First Search Algorithm

We all know the Depth First Search (DFS) Algorithm can be usually implemented in a Recursion fashion (easier and more straightforward than the non-recursive/iterative way with manually operating a stack). The DFS searches the entire tree which means it may lead to a solution quicker but may not be the optimal. Unlike DFS, the Breadth First Search algorithm expands and searches the tree level by level, thus the first solution will usually be the optimal (e.g. shortest, minimal cost etc).

The BackTracking algorithm is one of the DFS algorithm where the unnecesary branches of the tree are avoided whenever we can, if we know that a certain path will never reach a solution.

Given a list of integers, we can first sort them from the biggest to the smallest (non-ascending order). Thus, if we always pick the current maximum, add it to the pool, until the number is too big, we try next largest candidate. If a sum is smaller than 5, for example, then we will not try any candidates that are larger than 5 – which prunes quite a few unnecesary branches.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> r;
        if (candidates.size() == 0) {
            return r;
        }
        // largest to smallest order
        sort(begin(candidates), end(candidates), [](auto a, auto b) { return a > b; });        
        vector<int> cur = {};
        dfs(r, target, candidates, 0, cur);
        return r;
    }
private:
    void dfs(vector<vector<int>> &r, int target, vector<int>& candidates, int index, vector<int> &cur) {
        // find a combination, add it to the result solution
        if (target == 0) {
            r.push_back(cur);
        }
        for (int i = index; i < candidates.size(); ++ i) {
            // we can use this candidate                
            if (target >= candidates[i]) {
                cur.push_back(candidates[i]);                
                // backtracking with updated sum, and candidate no bigger than this one            
                dfs(r, target - candidates[i], candidates, i, cur);
                cur.pop_back();
            }
        }
    }
};

class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>> r;
        if (candidates.size() == 0) {
            return r;
        }
        // largest to smallest order
        sort(begin(candidates), end(candidates), [](auto a, auto b) { return a > b; });        
        vector<int> cur = {};
        dfs(r, target, candidates, 0, cur);
        return r;
    }
private:
    void dfs(vector<vector<int>> &r, int target, vector<int>& candidates, int index, vector<int> &cur) {
        // find a combination, add it to the result solution
        if (target == 0) {
            r.push_back(cur);
        }
        for (int i = index; i < candidates.size(); ++ i) {
            // we can use this candidate                
            if (target >= candidates[i]) {
                cur.push_back(candidates[i]);                
                // backtracking with updated sum, and candidate no bigger than this one            
                dfs(r, target - candidates[i], candidates, i, cur);
                cur.pop_back();
            }
        }
    }
};

The above backtracking algorithm is implemented using C++, with the recursion.

Knapsack Problems

• Teaching Kids Programming - 0/1 Knapsack: Length of the Longest Subsequence That Sums to Target (Recursion+Memoization=Top Down Dynamic Programming)
• Teaching Kids Programming - 0/1 Knapsack Space Optimised Dynamic Programming Algorithm
• Teaching Kids Programming - Using Bottom Up Dynamic Programming Algorithm to Solve 0/1 Knapsack Problem
• Teaching Kids Programming - 0/1 Knapsack Problem via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Bottom Up Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Multiple Strange Coin Flips/Toss Top Down Dynamic Programming Algorithm (Knapsack Variant)
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Max Profit of Rod Cutting (Unbounded Knapsack) via Top Down Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Bottom Up Dynamic Programming Algorithm
• Teaching Kids Programming - Brick Layout (Unlimited Knapsack) via Top Down Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Dynamic Programming Algorithm
• Count Multiset Sum (Knapsacks) by Recursive BackTracking Algorithm
• Dynamic Programming Algorithm to Solve the Poly Knapsack (Ubounded) Problem
• Dynamic Programming Algorithm to Solve 0-1 Knapsack Problem
• Classic Unlimited Knapsack Problem Variant: Coin Change via Dynamic Programming and Depth First Search Algorithm
• Classic Knapsack Problem Variant: Coin Change via Dynamic Programming and Breadth First Search Algorithm
• Complete Knapsack Problem
• 0/1 Knapsack Problem
• Teaching Kids Programming - Combination Sum Up to Target (Unique Numbers) by Dynamic Programming Algorithms
• Algorithms Series: 0/1 BackPack - Dynamic Programming and BackTracking
• Using BackTracking Algorithm to Find the Combination Integer Sum
• Facing Heads Probabilties of Tossing Strange Coins using Dynamic Programming Algorithm
• Partition Equal Subset Sum Algorithms using DFS, Top-Down and Bottom-up DP

–EOF (The Ultimate Computing & Technology Blog) —