lintcode 中等题：k Sum ii k数和 II

题目：

k数和 II

给定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<ArrayList<Integer>> kSumII(int A[], int k, int target) {
        // write your code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> path = new ArrayList<Integer>();
        helper(result, path,A,k,target,0);
        return result;
    }
    public void helper(ArrayList<ArrayList<Integer>> result,ArrayList<Integer> path,int [] A,int k ,int remain,int index){
        if( path.size() == k){
            if(remain ==0 )
                result.add(new ArrayList<Integer>(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);
        }
    }
}

View Code

总耗时: 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()

View Code