[LeetCode][216. Combination Sum III] 2 Approaches: Backtracking and Bit Mask

By Long Luo

This article is the solution 2 Approaches: Backtracking and Bit Mask of Problem 216. Combination Sum III.

Here shows 2 Approaches to slove this problem: Backtracking and Bit Mask.

Backtracking

A very easy backtracking solution. Just refer to 17. Letter Combinations of a Phone Number.

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();

    // corner cases
    if (k <= 0 || n <= 0 || k > n) {
        return ans;
    }

    // The upper bound of n: [9, 8, ... , (9 - k + 1)], sum is (19 - k) * k / 2
    if (n > (19 - k) * k / 2) {
        return ans;
    }

    backtrack(ans, new ArrayList<>(), 1, k, n);
    return ans;
}

public void backtrack(List<List<Integer>> res, List<Integer> path, int start, int k, int target) {
    if (k < 0 || target < 0) {
        return;
    }

    if (k == 0 && target == 0) {
        res.add(new ArrayList<>(path));
        return;
    }

    for (int i = start; i <= 9; i++) {
        // trim 
        if (i > target) {
            break;
        }
			
        // trim
        if (target - i == 0 && k > 1) {
            break;
        }

        path.add(i);
        backtrack(res, path, i + 1, k - 1, target - i);
        path.remove(path.size() - 1);
    }
}

Analysis

• Time Complexity: $O({M \choose k} \times k)$, $M$ is the size of combinations, $M = 9$, the total combinations is $M \choose k$.
• Space Complexity: $O(M + k)$, size of $path$ is $k$, the recursion stack is $O(M)$.

Bit Mask

Since the numbers are just from $1$ to $9$, the total sum of combinations is $2^9=512$.

We can map $1$ - $9$ with a number with a length of 9-bits number, bits $0$ means selecting $1$, bits $8$ means selecting $9$.

Eg:

$000000001b$, means [1]
$000000011b$, means [1,2]
$100000011b$, means [1,2,9]

We can search from $1$ to $512$, take the number corresponding to the bit value of $1$ in $i$, and sum it up to see if it is satisfied.

public List<List<Integer>> combinationSum3(int k, int n) {
    List<List<Integer>> ans = new ArrayList<>();

    // corner cases
    if (k <= 0 || n <= 0 || k > n) {
        return ans;
    }

    // The upper bound of n: [9, 8, ... , (9 - k + 1)], sum is (19 - k) * k / 2
    if (n > (19 - k) * k / 2) {
        return ans;
    }

    for (int mask = 0; mask < (1 << 9); mask++) {
        List<Integer> path = new ArrayList<>();
        if (check(path, mask, k, n)) {
            ans.add(path);
        }
    }

    return ans;
}

public boolean check(List<Integer> path, int mask, int k, int target) {
    path.clear();
    
    for (int i = 0; i < 9; i++) {
        if (((1 << i) & mask) != 0) {
            path.add(i + 1);
        }
    }

    if (path.size() != k) {
        return false;
    }

    int sum = 0;
    for (int x : path) {
        sum += x;
    }

    return sum == target;
}

Analysis

• Time Complexity: $O(M \times 2^M)$, $M = 9$, every state needs $O(M + k) = O(M)$ to check.
• Space Complexity: $O(M)$, $M$ is size of $\textit{path}$.

---

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗