clueless coding // TODO: be smarter

LeetCode 216. Combination Sum III: Java Solution



Problem Statement


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.

Function Signature (Java):
  public List<List<Integer>> combinationSum3(int k, int n)

Inputs:
  k = 3
  n = 7

Outputs:
[
  [1,2,4]
]

Inputs:
  k = 3
  n = 9

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



TL;DR Code 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);
	}
}