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

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 2.8k 阅读时长 ≈ 3 分钟

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.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
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.

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
31
32
33
34
35
36
37
38
39
40
41
42
43
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. 😉😃💗