# 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
`1`

through`9`

are 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 = 7Output:[[1,2,4]]Explanation:1 + 2 + 4 = 7 There are no other valid combinations.

**Example 2:**

Input:k = 3, n = 9Output:[[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 = 1Output:[]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 <= 9`

`1 <= 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