LeetCode Combination Sum II: DFS without Set

Overview

Backtracking (DFS) with pruning (stop search earlier if sum > target) could solve LeetCode Combination Sum II problem, no need to use set to handle duplicates.

LeetCode Combination Sum II

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

Each number in C may only be used once in the combination.

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 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

Analysis: DFS without Set

Basically, this question could be solve by using backtracking and pruning. Enumerate all the unique possible subsets, stop when the sum over the elements is larger than or equal to the given target. The following source code is accepted by LeetCode OJ to pass this Combination Sum II Problem:

vector< vector<int> > results;
vector<int>  ans;
vector<bool>  inSet;

void dfs(const vector<int> &cands, int i, int s, int t) {
    if (s > t || i > cands.size())
         return ;

    if (s == t) {
        results.push_back(ans);
        return ;
    }

    dfs(cands, i + 1, s, t);

    if (i == 0 || cands[i] != cands[i - 1] || inSet[i - 1]) {
        ans.push_back(cands[i]);
        inSet[i] = true;
        dfs(cands, i + 1, s + cands[i], t);
        ans.pop_back();
        inSet[i] = false;
    }
}

vector<vector<int> > combinationSum2(vector<int> &num, int target) {
    sort(num.begin(), num.end());
    inSet.resize(num.size());
    fill(inSet.begin(), inSet.end(), false);
    dfs(num, 0, 0, target);
    return results;
}

And you can find all the approaches to enumerate the subsets without duplicates in this post: “LeetCode Subsets I and II: DFS, Iterative (Bit Operation), Duplicate Handling“. Note the key fact to remove the duplicated subsets is to check the current number with the previous one, if they are of the same value, the number can only be used in the subset when the previous one is used already. Read that post for more details and STL set is not necessary to use at all.

  • Remark 1: Optional method could be using Dynamic Programming. And the recursive formula could possibly be this: let DP(T, n) denote the set of  unique subsets of the n elements given the target T, then we have DP(T, n) = DP(T, n-1) U {DP(T-An, n-1), An}, that is, DP(T, n) consist of the subsets from the n-1 elements which don’t contain the last element and those subsets which must contain the last element An and we find subset out of the n-1 elements give the target T-An (TO BE CONTINUED!) But in practice by the LeetCode OJ, it seems DFS is faster than DP approach.
  • Remark 2: Note this question actually is the subset sum problem which is NP-complete. It means that there is no efficient polynomial time algorithm to solve it for now.

Summary

Backtracking (DFS) with pruning (stop search earlier if sum > target) could solve LeetCode Combination Sum II problem, no need to use set to handle duplicates.

Written on April 27, 2013