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<>();
if (k <= 0 || n <= 0 || k > n) { return ans; }
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++) { if (i > target) { break; } 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((kM)×k), M is the size of combinations, M=9, the total combinations is (kM).
- 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 29=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<>();
if (k <= 0 || n <= 0 || k > n) { return ans; }
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), M=9, every state needs O(M+k)=O(M) to check.
- Space Complexity: O(M), M is size of 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. 😉😃💗