Combination Sum

文章目录

Combination Sum
- 题目
- 分析
- 代码如下

题目

题目链接：https://leetcode.com/problems/combination-sum
Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

All numbers (including target) will be positive integers.
The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
  [7],
  [2,2,3]
]

Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
  [2,2,2,2],
  [2,3,3],
  [3,5]
]

分析

题目给出一个包含不重复元素的int类型的数组candidates和一个目标数target。要求从candidates数组中找出所有可能的组合，这些数的和等于target，每个元素可以被多次选中。

可以使用递归的方法来求解这道题。

首先，对给出的数组candidates进行升序排序。使用一个count数组记录每一个元素使用的次数。
然后遍历整个数组（递归部分）。
假设当前为第i个元素，为起始元素，希望得到的和为target。
求出当前元素的最大个数max = target / candidates[i]。
- 如果max <= 0，由于后面的元素大于当前元素，所以直接return。
- 否则，不断循环减少max的值，直到为0。
  在每一轮循环中递归求解target = target - candidates[i] * temp，i = i + 1的情况，直到i = candicates.length时停止。
每次target为0时，根据count数组和candidates数组，添加当前结果的最终的结果链表中。然后return（由于target为0，后面的元素个数只能为0，所以直接回溯，寻找其他的情况）。

代码如下

class Solution { 
    public List<List<Integer>> combinationSum(int[] candidates, int target) { 
        List<List<Integer>> resultLists = new ArrayList<List<Integer>>();
        Arrays.sort(candidates);  // 排序
        int[] count = new int[candidates.length];
        combinationSum0(candidates, target, 0, count, resultLists);
        return resultLists;
    }
    private void combinationSum0(int[] candidates, int target, int start,
            int[] count, List<List<Integer>> resultLists) { 
        if (target == 0) {   // 已经完成目标
            addList(count, candidates, resultLists);
            return;
        }
        if (start >= candidates.length) {   // 超出范围
            return;
        }
        int temp = candidates[start];  // 数组的最小值
        int max = target / temp;  // 最多能有几个
        if (max <= 0) {   // 最多能有0个
            return;
        }
        for (int i = max; i >= 0; i--) { 
            count[start] = i;
            combinationSum0(candidates, target - i * temp, start + 1, count, resultLists);
        }
        // 因为会回溯，count[start]需要为0
        // 但是这这一步没有也没关系。
        // 因为在上面的循环中，i最后时0，count[start]一定会被置为0。
        count[start] = 0;
    }
    // 添加结果到结果链表中
    private void addList(int[] count, int[] candidates, List<List<Integer>> resultLists) { 
        List<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < count.length; i++) { 
            for (int j = 0; j < count[i]; j++) { 
                list.add(candidates[i]);
            }
        }
        resultLists.add(list);
    }
}