Find all possible combinations of

*k*numbers that add up to a number*n*, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.

*Example 1:*

Input:

*k*= 3,*n*= 7
Output:

[[1,2,4]]

*Example 2:*

Input:

*k*= 3,*n*= 9
Output:

[[1,2,6], [1,3,5], [2,3,4]]

**Understand the problem:**

A very classic back tracking problem.

**Code (Java):**

public class Solution { public List<List<Integer>> combinationSum3(int k, int n) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if (k <= 0 || n <= 0) { return result; } List<Integer> curr = new ArrayList<Integer>(); combinationSum3Helper(1, n, 0, k, 0, curr, result); return result; } private void combinationSum3Helper(int start, int n, int count, int k, int curSum, List<Integer> curr, List<List<Integer>> result) { if (count > k) { return; } if (curSum == n && count == k) { result.add(new ArrayList<Integer>(curr)); return; } for (int i = start; i <= 9; i++) { if (curSum + i > n) { break; } curr.add(i); combinationSum3Helper(i + 1, n, count + 1, k, curSum + i, curr, result); curr.remove(curr.size() - 1); } } }

## No comments:

## Post a Comment