Combination Sum Series

I worked through all the Combination Sum problems in one go. This gave me a deeper understanding of backtracking and exhaustive search. Here’s what I learned.

Core Idea

Choose recursively, then backtrack that choice. This pattern works well for combinatorial search problems.

void Sum(int begin, vector<T> path, vector<T> candi, ...) {
	if(meets end condition) return;

	// Search all elements in range
	for(i=begin...N) {
		// Choose this element
		path.push_back(candi[i]);
		// Call Sum(..) to keep searching
		path.pop_back(); // backtrack
	}
}

The rest is just template code.

// Combination Sum
// The candidate array has no duplicates, but we can reuse elements
class Solution {
public:
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        calSum(candidates, 0, target);
        return res;
    }
    
    void calSum(vector<int>& candi, int begin, int target) {
        if (!target) {
            res.push_back(path);
            return;
        }
		// Sorted arrays help with pruning
        for(int i=begin;i<candi.size()&&candi[i]<=target;++i) {
            path.push_back(candi[i]);
            calSum(candi, i, target-candi[i]);
            path.pop_back();
        }
    }
    
    vector<int> path;
    vector<vector<int>> res;
};

// Combination Sum II
// The candidate array has duplicates, each element used once
class Solution {
public:
    vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        calSum(candidates, 0, target);
        return res;
    }
    
    void calSum(vector<int>& candi, int begin, int target) {
        if (!target) {
            res.push_back(path);
            return;
        }
        for(int i=begin;i<candi.size()&&candi[i]<=target;++i) {
			// Sorted arrays help remove duplicates
            if (begin==i || candi[i] != candi[i-1]) {
                path.push_back(candi[i]);
                calSum(candi, i+1, target-candi[i]);
                path.pop_back();
            }
        }
    }
    
    vector<int> path;
    vector<vector<int>> res;
};

// Combination Sum III
// Choose from 1 to 9 only, no repeated selections
class Solution {
public:
    vector<vector<int>> combinationSum3(int k, int n) {
        vector<int> candi;
        for(int i=1;i<=9;++i) candi.push_back(i);
        calSum(candi, 0, n, k);
        return res;
    }
    
    void calSum(vector<int>& candi, int begin, int target, int k) {
        if (!target) {
            if (k==0) res.push_back(path);
            return;
        }
        if (!k) return;
        for(int i=begin;i<candi.size()&&candi[i]<=target;++i) {
            path.push_back(candi[i]);
            calSum(candi, i+1, target-candi[i], k-1);
            path.pop_back();
        }
    }
    
    vector<int> path;
    vector<vector<int>> res;
};

#recursion #backtracking

Candy Distribution Algorithm Common STL Operations