LeetCode Combination Sum: DFS no Sort or Set

Overview

Backtracking (DFS) with pruning could solve LeetCode Combination Sum, and there is no need to sort the input or using set to remove duplicate results.

LeetCode Combination Sum

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 (a1a2, … , 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]

Solution Analysis: DFS and no Sort or Set

Essentially, this is a backtracking problem, so DFS and pruning should work here: Use DFS to search though all the possible solution space, stop when the combination sum is larger than or equal to the given target (because all of the numbers in this problem are assumed to be positive). And note for each candidate, we only need to test those bigger than or equal to the previous number added in previous step or level in the DFS tree. The folloinwg source code is accepted by the LeetCode OJ to pass this Combination Sum problem and I will give more elaboration after the source code:

class Solution {
    public:
        vector<vector<int>> results;
        vector<int> ans;
        void dfs(const vector<int> &cands, int s, int t) {
            if (s > t) return ;
            if (s == t) {
                results.push_back(ans);
                return ;
            }
            for (int i = 0; i < cands.size(); ++i) {
                if (ans.empty() || cands[i] >= ans.back()) {
                    ans.push_back(cands[i]);
                    dfs(cands, s + cands[i], t);
                    ans.pop_back();
                }
            }
        }
        vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
            results.clear(), ans.clear();
            dfs(candidates, 0, target);
            return results;
        }

};

Elaboration

  1. Some people might want to sort the input candidates first, but that is not necessary, you can think about why
  2. Using set is not helpful at all to remove the duplicates in the returned results. Think about this case to find combination sum equal to five among [1, 2], simply adopting DFS would give 1 2 2 and 2 2 1, these two are the same actually but set cannot distinguish them successfully, that is why we need to check the current one against the previous added number in the code
  3. The trick used in the code is to form the combination only use those which are larger than or equal to the previously added number, this not only keep the requests in non-descending order, but also keep avoid duplicated result combination (why?) and a third advantage is to eliminate the sorting for the input candidates.
  4. Question: I do not have a clear or detailed derivation for the time complexity yet, I only have rough idea that the time complexity would be exponential, but the detailed proof or any useful hints on that is not very clear to me. Anyone could help on this? Thanks a lot
  5. Question: There could be DP solutions too, but the recursive dp formula is difficult to derive, again, if you have any idea on it, please help me and share your comments. Thanks again!
  6. One could check this post for reference: Print All Combinations of a Number as a Sum of Candidate Numbers

Summary

Backtracking (DFS) with pruning could solve LeetCode Combination Sum, and there is no need to sort the input or using set to remove duplicate results.

Written on April 27, 2013