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

By Long Luo

This article is the solution 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((Mk)×k)O({M \choose k} \times k), MM is the size of combinations, M=9M = 9, the total combinations is (Mk)M \choose k.

  • Space Complexity: O(M+k)O(M + k), size of pathpath is kk, the recursion stack is O(M)O(M).

Bit Mask

Since the numbers are just from 11 to 99, the total sum of combinations is 29=5122^9=512.

We can map 11 - 99 with a number with a length of 9-bits number, bits 00 means selecting 11, bits 88 means selecting 99.

Eg:

000000001b000000001b, means [1]
000000011b000000011b, means [1,2]
100000011b100000011b, means [1,2,9]

We can search from 11 to 512512, 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×2M)O(M \times 2^M), M=9M = 9, every state needs O(M+k)=O(M)O(M + k) = O(M) to check.

  • Space Complexity: O(M)O(M), MM is size of path\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. 😉😃💗