Table of Contents
Combination Sum III – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Find all valid combinations of k numbers that sum up to n such that the following conditions are true:
- Only numbers
1through9are used. - Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.
Example 1:
Input: k = 3, n = 7 Output: [[1,2,4]] Explanation: 1 + 2 + 4 = 7 There are no other valid combinations.
Example 2:
Input: k = 3, n = 9 Output: [[1,2,6],[1,3,5],[2,3,4]] Explanation: 1 + 2 + 6 = 9 1 + 3 + 5 = 9 2 + 3 + 4 = 9 There are no other valid combinations.
Example 3:
Input: k = 4, n = 1 Output: [] Explanation: There are no valid combinations. Using 4 different numbers in the range [1,9], the smallest sum we can get is 1+2+3+4 = 10 and since 10 > 1, there are no valid combination.
Constraints:
2 <= k <= 91 <= n <= 60
C++ Combination Sum III LeetCode Solution
class Solution {
public:
void combination(vector<vector<int>>& result, vector<int> sol, int k, int n) {
if (sol.size() == k && n == 0) { result.push_back(sol); return ; }
if (sol.size() < k) {
for (int i = sol.empty() ? 1 : sol.back() + 1; i <= 9; ++i) {
if (n - i < 0) break;
sol.push_back(i);
combination(result, sol, k, n - i);
sol.pop_back();
}
}
}
vector<vector<int>> combinationSum3(int k, int n) {
vector<vector<int>> result;
vector<int> sol;
combination(result, sol, k, n);
return result;
}
};
Java Combination Sum III LeetCode Solution
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> ans = new ArrayList<>();
combination(ans, new ArrayList<Integer>(), k, 1, n);
return ans;
}
private void combination(List<List<Integer>> ans, List<Integer> comb, int k, int start, int n) {
if (comb.size() == k && n == 0) {
List<Integer> li = new ArrayList<Integer>(comb);
ans.add(li);
return;
}
for (int i = start; i <= 9; i++) {
comb.add(i);
combination(ans, comb, k, i+1, n-i);
comb.remove(comb.size() - 1);
}
}
Python 3 Combination Sum III LeetCode Solution
class Solution(object):
def combinationSum3(self, k, n):
ret = []
self.dfs(list(range(1, 10)), k, n, [], ret)
return ret
def dfs(self, nums, k, n, path, ret):
if k < 0 or n < 0:
return
if k == 0 and n == 0:
ret.append(path)
for i in range(len(nums)):
self.dfs(nums[i+1:], k-1, n-nums[i], path+[nums[i]], ret)
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below
