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

ゝ一世哀愁。 2022-09-03 07:28 170阅读 0赞

## 题目 ##

[https://leetcode.com/problems/combination-sum/][https_leetcode.com_problems_combination-sum]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

不是最优解法。

对于每一个位置 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]);
                }
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_combination-sum]: https://leetcode.com/problems/combination-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/4c36a0d11bb64ed8859ab23ce4fd56a7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/24b29ab7fa3c424b8b9c4ac40a0aaaea.png