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; }
publicbooleancheck(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) { returnfalse; }
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:-)