Combination

1. 기본 조합 (Combinations)

• 문제: 주어진 배열에서 k개의 원소를 선택하는 모든 조합을 구합니다.

java코드 복사void combine(int[] nums, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrack(result, new ArrayList<>(), nums, k, 0);
    for (List<Integer> combination : result) {
        System.out.println(combination);
    }
}

void backtrack(List<List<Integer>> result, List<Integer> tempList, int[] nums, int k, int start) {
    if (tempList.size() == k) {
        result.add(new ArrayList<>(tempList));
        return;
    }

    for (int i = start; i < nums.length; i++) {
        tempList.add(nums[i]);
        backtrack(result, tempList, nums, k, i + 1);
        tempList.remove(tempList.size() - 1);  // 백트래킹
    }
}

---

2. 중복 허용 조합 (Combinations with Repetition)

• 문제: 중복을 허용하여 k개의 원소를 선택하는 모든 조합을 구합니다.

java코드 복사void combineWithRepetition(int[] nums, int k) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackRepetition(result, new ArrayList<>(), nums, k, 0);
    for (List<Integer> combination : result) {
        System.out.println(combination);
    }
}

void backtrackRepetition(List<List<Integer>> result, List<Integer> tempList, int[] nums, int k, int start) {
    if (tempList.size() == k) {
        result.add(new ArrayList<>(tempList));
        return;
    }

    for (int i = start; i < nums.length; i++) {
        tempList.add(nums[i]);
        backtrackRepetition(result, tempList, nums, k, i);  // 중복을 허용하므로 i를 다시 사용
        tempList.remove(tempList.size() - 1);  // 백트래킹
    }
}

---

3. 조합의 합 (Combination Sum)

• 문제: 주어진 배열에서 중복을 허용하여 원소의 합이 target이 되는 모든 조합을 구합니다.

java코드 복사void combinationSum(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    backtrackSum(result, new ArrayList<>(), candidates, target, 0);
    for (List<Integer> combination : result) {
        System.out.println(combination);
    }
}

void backtrackSum(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
    if (remain < 0) return;  // 합이 target을 넘으면 종료
    if (remain == 0) {
        result.add(new ArrayList<>(tempList));  // target을 맞춘 경우
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        tempList.add(candidates[i]);
        backtrackSum(result, tempList, candidates, remain - candidates[i], i);  // 중복을 허용하여 동일한 요소를 다시 사용 가능
        tempList.remove(tempList.size() - 1);  // 백트래킹
    }
}

---

4. 조합의 합 2 (Combination Sum II)

• 문제: 주어진 배열에서 중복을 허용하지 않고, 원소의 합이 target이 되는 모든 조합을 구합니다. 배열에는 중복된 값이 포함될 수 있지만, 같은 숫자는 한 번만 사용할 수 있습니다.

java코드 복사void combinationSum2(int[] candidates, int target) {
    List<List<Integer>> result = new ArrayList<>();
    Arrays.sort(candidates);  // 중복된 값을 처리하기 위해 정렬
    backtrackSum2(result, new ArrayList<>(), candidates, target, 0);
    for (List<Integer> combination : result) {
        System.out.println(combination);
    }
}

void backtrackSum2(List<List<Integer>> result, List<Integer> tempList, int[] candidates, int remain, int start) {
    if (remain < 0) return;  // 합이 target을 넘으면 종료
    if (remain == 0) {
        result.add(new ArrayList<>(tempList));  // target을 맞춘 경우
        return;
    }

    for (int i = start; i < candidates.length; i++) {
        if (i > start && candidates[i] == candidates[i - 1]) continue;  // 중복 제거
        tempList.add(candidates[i]);
        backtrackSum2(result, tempList, candidates, remain - candidates[i], i + 1);  // 중복 허용하지 않음
        tempList.remove(tempList.size() - 1);  // 백트래킹
    }
}

---

5. 조합의 수 계산 (nCk)

• 문제: n개의 원소 중에서 k개의 원소를 선택하는 경우의 수를 계산합니다.

java코드 복사int combination(int n, int k) {
    if (k == 0 || k == n) {
        return 1;
    }
    return combination(n - 1, k - 1) + combination(n - 1, k);
}