Combination Sum

墨蓝 2023-06-09 14:30 50阅读 0赞

# Combination Sum #

### 文章目录 ###

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

## 题目 ##

题目链接：[https://leetcode.com/problems/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);
        }
    }

[https_leetcode.com_problems_combination-sum]: https://leetcode.com/problems/combination-sum