题目：

给定n个不同的正整数，整数k（1<= k <= n）以及一个目标数字。　　　　

在这n个数里面找出K个数，使得这K个数的和等于目标数字，你需要找出所有满足要求的方案。

样例

给出[1,2,3,4]，k=2， target=5，返回 [[1,4],[2,3]]

解题：

题目中限制的条件很多，A数组中的各个数字都不相等，A中k个数的和是 target  

问题：

1.在所有的组合方式中，A[i] 是否会重复，也就是说，A[i] ,即在{a，b，A[i]} 也在{a1，b1，A[i]}中。

可能：如A = {1,2,3,4,5} 3个数的和等于8的可能方式有：{1,2,5} 和{1,3,4}

思路：

根据深度优先变量的思想解决问题：

1.跳出点，target ==0  k ==0 时候，这条路径保存下来

k==0 但是target！=0时候说明路径中有k个数，但是target不满足条件，不保存。

2.递归过程：

对当前点加入到路径path中

从当前点的小一点开始 考虑：A中 k-1 个数的和target-A[i] 的情况

上面

Java程序：

public class Solution {    /**     * @param A: an integer array.     * @param k: a positive integer (k <= length(A))     * @param target: a integer     * @return a list of lists of integer      */     public ArrayList
      
       
        > kSumII(int A[], int k, int target) {        // write your code here        ArrayList
        
         
          > result = new ArrayList
          
           
            >(); ArrayList
            
              path = new ArrayList
             
              (); helper(result, path,A,k,target,0); return result; } public void helper(ArrayList
              
               
                > result,ArrayList
                
                  path,int [] A,int k ,int remain,int index){ if( path.size() == k){ if(remain ==0 ) result.add(new ArrayList
                 
                  (path)); else return; } for(int i = index;i< A.length ;i++){ path.add(A[i]); helper(result,path,A,k,remain - A[i],i+1); path.remove(path.size() - 1); } }}
                 
                
               
              
             
            
           
          
         
        
       
      

总耗时: 4268 ms

Python程序：

 下面程序运行有问题，还不知道怎么修改

class Solution:    """    @param A: An integer array.    @param k: A positive integer (k <= length(A))    @param target: Integer    @return a list of lists of integer     """    def kSumII(self, A, k, target):        # write your code here        path = []        result = []        self.helper(result,path,A,k,target,0)        return result        def helper(self,result , path ,A ,k,target,index):                if len(path) == k:            if target==0:                result.append(path[:])        else:             for i in range(index,len(A)):                path.append(A[i])                self.helper(result,path,A,k,target - A[i] ,index + 1)                path.pop()