本文共 2355 字，大约阅读时间需要 7 分钟。

1、题目描述

    输出一个数组和一个目标值，数组中不包含重复元素，找出数组中所有的元素序列，这些元素的和为目标值，元素序列可重复。比如说输入数组：[2,3,5]，输入目标值：8，那么输出为：[  [2,2,2,2],  [2,3,3],  [3,5] ]

2、解题思路

    这个题目有点复杂，即使用暴力解也不一定马上想到思路。由于序列中的元素可以重复使用，给这道题目增加了难度。一种可行的解法是采用递归的思想来求解。在主函数中，以输入数组的每个元素为起点，循环调用递归函数，直到遍历到输入数组结束。在递归函数中，需要使用一个数组来保存已经使用到的元素，并且传入需要判断的下一个元素和本次递归的目标值。在递归函数中判断目标值减去该元素的大小：

• 如果目标值等于当前元素值，那么则找到一种组合方式，将这个元素压入数组中，并将数组作为一种可行的结果。
• 如果目标值小于当前元素值，那么不考虑当前元素，直接返回；
• 如果目标值大于当前元素值，那么更新目标值，把当前元素值压入数据中，使用一个循环调用递归函数，起始元素为当前元素，终止元素为输入数组的最后一个元素。循环完成之后，弹出数组的最后一个元素，返回上一层递归。

代码如下：

void find(vector
   
     &input, vector
    
     
      > &output, vector
      
        &elem, int index, int target) {	elem.push_back(input[index]);	if (target - input[index] == 0)     //目标值等于当前值，找到一个可行的组合	{		output.push_back(elem);		elem.pop_back();		return;	}	if (target - input[index] < 0)	{  //目标值小于当前值，直接返回		elem.pop_back();		return;	} 	if (target - input[index] > 0)      //目标值大于当前值，更新目标值，接着进行递归	{		target = target - input[index];		for (int j = index; j < input.size(); j++) {				if (target >= input[j]) {				find(input, output, elem, j, target);			}		}		elem.pop_back();	}}vector
       
        
         > combinationSum(vector
         
          & candidates, int target) { vector
          
           
            > output; vector
            
              elem; for (int i = 0; i
            
           
          
         
        
       
      
     
    
   

3、题目拓展

    如果要求序列中元素不能重复，那需要怎么解决呢？只需要对上述代码进行修改即可，代码如下：

void find(vector
   
     &input, vector
    
     
      > &output, vector
      
        &elem, int index, int target) {	elem.push_back(input[index]);	if (target - input[index] == 0)     //目标值等于当前值，找到一个可行的组合	{		output.push_back(elem);		elem.pop_back();		return;	}	if (target - input[index] < 0)	{  //目标值小于当前值，直接返回		elem.pop_back();		return;	} 	if (target - input[index] > 0)      //目标值大于当前值，更新目标值，接着进行递归	{		target = target - input[index];		for (int j = index + 1; j < input.size(); j++) {	//在这里修改，把index改为index + 1			if (target >= input[j]) {				find(input, output, elem, j, target);			}		}		elem.pop_back();	}}vector
       
        
         > combinationSum(vector
         
          & candidates, int target) { vector
          
           
            > output; vector
            
              elem; for (int i = 0; i
            
           
          
         
        
       
      
     
    
   

    只需要将第三种情况下，循环调用递归函数的起始值改为下一个元素开始遍历即可，其它地方不用修改。