Combinations v.s Combination Sum III (Java)

• These two questions are very similar, so here I am going to put these two questions into comparisons.

In Combinations, given `k` is the length of the sub-list, `n` is the last number of combination, return all possible combinations of k numbers out of 1 ... n.

In Combination Sum III, `k` is the length of the sub-list, `n` is the target sum, return all possible combinations of k numbers that add up to `n`. Here, we limit the number used from 1 to 9.

What's the similarities?

1. Both start at `1`
2. Combinations ends ranges from `n - k + 1` to `n` , Combination Sum III from `1` to `9`
3. Combinations adds sub-list when sub-list size is equal to `k`, Combination Sum III adds sub-list when sub-list size is equal to `k` and remaining equals `0` (subtract `i` from `n` in loop)

Combinations :

``````public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<Integer>(), k, 1, n - k + 1);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int start, int end) {
if (tempList.size() == k) list.add(new ArrayList<>(tempList));
else{
for (int i = start; i <= end; i++) {
backtrack(list, tempList, k, i + 1, end + 1);
tempList.remove(tempList.size() - 1);
}
}
}
``````

Combination Sum III :

``````public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> list = new ArrayList<>();
backtrack(list, new ArrayList<Integer>(), k, n, 1);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int k, int remain, int start) {
if(tempList.size() == k && remain == 0) list.add(new ArrayList<>(tempList));
else{
for(int i = start; i <= 9; i++) {
• @issac3 Thanks for detailed analysis. but why does Combination range start from `n - k + 1`? This is the only part that eludes me. Can you please help withe the reasoning behind this? Thanks.