Algorithm
Problem Name: 216. Combination Sum III
Problem Link:https://leetcode.com/problems/combination-sum-iii/
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
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
vector < vector<int> > combinationSum3(int k, int n) {
vector < vector<int> > ans;
vector<int> temp;
combinationSum3Helper(1, n, k, temp, ans);
return ans;
}
void combinationSum3Helper(int start, int n, int k, vector<int> &temp, vector < vector<int> > &ans) {
if (k == temp.size() && n == 0) {
ans.push_back(temp);
return;
}
else if (temp.size() > k || n < 0) {
return;
}
for (int i = start; i < = 9; i++) {
temp.push_back(i);
combinationSum3Helper(i + 1, n - i, k, temp, ans);
temp.pop_back();
}
}
};
int main() {
int k = 3;
int n = 7;
Solution s;
vector < vector<int> > ans = s.combinationSum3(k, n);
for (int i = 0; i < ans.size(); i++) {
for (int j = 0; j < ans[i].size(); j++) {
printf("%d ", ans[i][j]);
}
printf("\n");
}
return 0;
}
Input
k = 3, n = 7
Output
[[1,2,4]]
#2 Code Example with Java Programming
Code -
Java Programming
class Solution {
public List();
helper(n, lists, new ArrayList<>(), 0, k, 1);
return lists;
}
private void helper(int n, List < List list, int currSum, int k, int currNum) {
if (list.size() == k) {
if (currSum == n) {
lists.add(new ArrayList<>(list));
}
return;
}
for (int i = currNum; i < = 9; i++) {
list.add(i);
helper(n, lists, list, currSum + i, k, i + 1);
list.remove(list.size() - 1);
}
}
}
Input
k = 3, n = 7
Output
[[1,2,4]]
#3 Code Example with Javascript Programming
Code -
Javascript Programming
const combinationSum3 = function(k, n) {
const ans = [];
combination(ans, [], k, 1, n);
return ans;
};
function combination(ans, comb, k, start, n) {
if (comb.length > k) {
return;
}
if (comb.length === k && n === 0) {
ans.push(comb.slice(0));
return;
}
for (let i = start; i < = n && i <= 9; i++) {
comb.push(i);
combination(ans, comb, k, i + 1, n - i);
comb.pop();
}
}
Input
k = 3, n = 9
Output
[[1,2,6],[1,3,5],[2,3,4]]
#4 Code Example with Python Programming
Code -
Python Programming
class Solution:
def combinationSum3(self, k, n):
"""
:type k: int
:type n: int
:rtype: List[List[int]]
"""
stack, nums, res = [(0, [], 0, k)], range(1, 10), []
while stack:
sm, tmp, index, k_val = stack.pop(0)
for i in range(index, len(nums)):
if sm + nums[i] < n and k_val > 0: stack.append((sm + nums[i], tmp + [nums[i]], i + 1, k_val - 1))
elif sm + nums[i] == n and k_val == 1: res.append(tmp + [nums[i]])
return res
Input
k = 3, n = 9
Output
[[1,2,6],[1,3,5],[2,3,4]]
#5 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
using System.Linq;
namespace LeetCode
{
public class _0216_CombinationSumIII
{
public IList < IList<int>> CombinationSum3(int k, int n)
{
var results = new List < IList<int>>();
Helper(0, k, n, new List < int>(), results);
return results;
}
private void Helper(int index, int k, int n, IList < int> current, IList= k || n < 0) return;
var start = index == 0 ? 1 : current.Last() + 1;
for (int i = start; i < = n && i < 10; i++)
{
var newList = new List<int>(current);
newList.Add(i);
Helper(index + 1, k, n - i, newList, results);
}
}
}
}
Input
k = 4, n = 1
Output
[]