216. Combination Sum III

Find all valid combinations of 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 = 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 <= 9
• 1 <= n <= 60

---

216. 조합의 합 III

n의 합계가 되는 모든 유효한 숫자 조합을 찾으십시오. 다음 조건이 참인 경우:

• 숫자 1에서 9까지만 사용됩니다.
• 각 숫자는 최대 한 번 사용됩니다.

모든 가능한 유효한 조합의 목록을 반환하십시오. 목록에는 동일한 조합이 두 번 포함되어서는 안되며, 조합은 어떤 순서로든 반환될 수 있습니다.

예제 1:

입력: k = 3, n = 7
출력: [[1,2,4]]
설명:
1 + 2 + 4 = 7
다른 유효한 조합은 없습니다.

예제 2:

입력: k = 3, n = 9
출력: [[1,2,6],[1,3,5],[2,3,4]]
설명:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
다른 유효한 조합은 없습니다.

예제 3:

입력: k = 4, n = 1
출력: []
설명: 유효한 조합이 없습니다.
[1,9] 범위 내에서 4개의 다른 숫자를 사용할 때, 얻을 수 있는 가장 작은 합은 1+2+3+4 = 10이고, 10 > 1 이므로 유효한 조합이 없습니다.

제약 사항:

• 2 <= k <= 9
• 1 <= n <= 60

Solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };  // 1부터 9까지의 숫자 배열

    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        combination(result, new ArrayList<>(), 0, k, n, 0);
        return result;
    }

    private void combination(List<List<Integer>> combinations, List<Integer> currentCombination, int index, int k,
            int n, int sum) {
        if (currentCombination.size() == k && sum == n) { // k개의 숫자가 사용되고, 합이 n과 같은 경우
            combinations.add(new ArrayList<>(currentCombination)); // 결과 리스트에 추가
            return;
        }

        for (int i = index; i < numbers.length; i++) {
            if (sum + numbers[i] <= n) { // 현재 숫자를 추가했을 때 합이 n을 초과하지 않는 경우
                currentCombination.add(numbers[i]); // 숫자 추가
                combination(combinations, currentCombination, i + 1, k, n, sum + numbers[i]); // 재귀 호출
                currentCombination.remove(currentCombination.size() - 1); // 마지막 요소 제거 (백트래킹)
            }
        }
    }
}