leetcode 39. Combination Sum | 39. 组合总和（Java）-蒲公英云

leetcode 39. Combination Sum | 39. 组合总和（Java）

题目

https://leetcode.com/problems/combination-sum/
在这里插入图片描述

题解

不是最优解法。

对于每一个位置 i 上的元素，分为选或不选两种情况。
遍历每一个位置，计算强制选择当前元素的情况下，后面的元素怎么处理。
因为每一个元素都被强制选过，所以不会有遗漏。

class Solution { 
    Set<List<Integer>> set;
    public List<List<Integer>> combinationSum(int[] arr, int target) { 
        Arrays.sort(arr);
        set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) { 
            List<Integer> list = new ArrayList<>();
            list.add(arr[i]);
            process(list, i, arr, target - arr[i]); // 强制加入i位置元素
        }
        return new ArrayList<>(set);
    }
    public void process(List<Integer> list, int i, int[] arr, int target) { 
        List<Integer> newList;
        if (target == 0) { 
            newList = new ArrayList<>(list);
            set.add(newList);
        } else if (target > 0) { 
            for (int j = i; j < arr.length; j++) {  // 不用管前面，前面已经保证过了
                newList = new ArrayList<>(list);
                newList.add(arr[j]);
                process(newList, j, arr, target - arr[j]);
            }
        }
    }
}