// @Title: 组合总和 (Combination Sum)
// @Author: qisiii
// @Date: 2024-04-26 13:43:42
// @Runtime: 2 ms
// @Memory: 43.7 MB
// @comment: 
// @flag: 
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        return doSolution(candidates, 0, candidates.length - 1, target);

    }

    private List<List<Integer>> doSolution(int[] candidates, int left, int right, int target) {
        List<List<Integer>> result = new ArrayList<>();
        while (left <= right) {
            if (candidates[right] == target) {
                result.add(new ArrayList<>(Arrays.asList(candidates[right])));
            } else if (candidates[right] < target) {
                List<List<Integer>> temp = doSolution(candidates, left, right, target - candidates[right]);
                for(int i=0;i<temp.size();i++){
                    temp.get(i).add(candidates[right]);
                }
                result.addAll(temp);
            }
            right--;
        }
        return result;
    }
}

// @Title: 组合总和 (Combination Sum)
// @Author: qisiii
// @Date: 2024-09-19 22:43:39
// @Runtime: 2 ms
// @Memory: 43.5 MB
// @comment: 
// @flag: 
class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        dfs(result, new ArrayList<>(), candidates, target,0);
        return result;
    }

    private void dfs(List<List<Integer>> result, List<Integer> list, int[] candidates, int target,int index) {
        if (target == 0) {
            result.add(new ArrayList<>(list));
            return;
        }
        //注意，i从index开始是为了避免重复;
        //以[2,3,6,7]为例,[2,2,3],[2,3,2],[3,2,2]其实都是相同的结果,
        //2,2,3表示的是选择第一个，第一个，第二个，表示为(112),当固定前两种选择的时候，该字数会尝试所有可能的情况,比如111,113,114；因此当第二个数字为3时，可理解为12x，由于已经尝试过112，因此无需再尝试比当前位靠前的情况
        for (int i = index; i < candidates.length; i++) {
            int temp = candidates[i];
            // 由于已经排序，当该元素大于target，则后续值都没有比较的意义了
            if (temp > target) {
                return;
            }
            list.add(temp);
            dfs(result, list, candidates, target - temp,i);
            list.remove(list.size() - 1);
        }

    }
}