39. 組み合わせ合計問題（重複選択可）

整数配列candidatesと目標値targetが与えられたとき、配列要素の和がtargetとなる全てのユニークな組み合わせを返します。各要素は無制限に再利用可能です。

入力例: candidates = [2,3,6,7], target = 7
出力例: [[2,2,3],[7]]

解法ポイント:

• 要素の重複使用を許可するため、再帰呼び出し時にインデックスを進めない
• 枝刈り処理で不要な探索を省略

import java.util.*;

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> track = new LinkedList<>();
    
    public List<List<Integer>> combinationSum(int[] nums, int target) {
        Arrays.sort(nums);
        backtrack(nums, target, 0, 0);
        return res;
    }
    
    void backtrack(int[] nums, int target, int currentSum, int start) {
        if(currentSum == target) {
            res.add(new ArrayList<>(track));
            return;
        }
        if(currentSum > target) return;
        
        for(int i = start; i < nums.length; i++) {
            track.add(nums[i]);
            backtrack(nums, target, currentSum + nums[i], i);
            track.removeLast();
        }
    }
}

40. 組み合わせ合計問題（重複選択不可）

配列要素の重複使用を禁止し、かつ解の重複も排除するバージョンです。

入力例: candidates = [10,1,2,7,6,1,5], target = 8
出力例: [[1,1,6],[1,2,5],[1,7],[2,6]]

解法ポイント:

• 配列を事前ソート
• 重複要素のスキップ処理
• インデックスを進めて要素の再利用を防止

import java.util.*;

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    LinkedList<Integer> track = new LinkedList<>();
    
    public List<List<Integer>> combinationSum2(int[] nums, int target) {
        Arrays.sort(nums);
        backtrack(nums, target, 0, 0);
        return res;
    }
    
    void backtrack(int[] nums, int target, int currentSum, int start) {
        if(currentSum == target) {
            res.add(new ArrayList<>(track));
            return;
        }
        if(currentSum > target) return;
        
        for(int i = start; i < nums.length; i++) {
            if(i > start && nums[i] == nums[i-1]) continue;
            
            track.add(nums[i]);
            backtrack(nums, target, currentSum + nums[i], i+1);
            track.removeLast();
        }
    }
}