90 k数和 II

2018/07/16 20:06
阅读数 0

原题网址:https://www.lintcode.com/problem/k-sum-ii/description

描述

Given n unique integers, number k (1<=k<=n) and target.

Find all possible k integers where their sum is target.

您在真实的面试中是否遇到过这个题?  是

样例

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

 

标签
LintCode 版权所有
Depth-first Search(DFS)
 
 
思路:深度优先搜索(DFS是一个递归的过程)。
创建递归函数,从原数组起始位置开始搜索,每个元素都有两种情况,拿或者不拿。
递归搜索终止条件为:
1.若拿到的元素个数等于K且元素的和等于target,说明找到一组解,将其push到结果数组中;
2.搜索指针超出原数组下标范围;
3.拿到元素的个数大于等于K且元素的和不为target或者元素的和已经大于target,结束当前搜索。(剪枝?)
 
 
 AC代码:
class Solution {
public:
    /*
     * @param A: an integer array
     * @param k: a postive integer <= length(A)
     * @param target: an integer
     * @return: A list of lists of integer
     */
    vector<vector<int>> kSumII(vector<int> &A, int k, int targer) {
        // write your code here
    vector<vector<int>> result;
    vector<int> cur;
    int sum=0;
    dfsn(A,k,targer,sum,0,cur,result);
    return result;
    }
    
    void dfsn(vector<int> &A, int k, int targer,int sum,int ind,vector<int> cur ,vector<vector<int>> &result)
{
    if (cur.size()==k&&sum==targer)
    {
        result.push_back(cur);
        return ;
    }
    if (ind>=(int)A.size())
    {
        return ;
    }
    if (cur.size()>=k||sum>targer)
    {
        return ;
    }
    cur.push_back(A[ind]);
    dfsn(A,k,targer,sum+A[ind],ind+1,cur,result);
    cur.pop_back();//去掉A[ind];
    dfsn(A,k,targer,sum,ind+1,cur,result);
}
}; 

 

PS:从第一个元素开始,依次拿走K个元素组成cur,每个元素只有两种情况,当前被拿到、当前没被拿到,这样就可以找到所有K个数的组合。K数和为target就push到结果中,否则废弃。

进一步剪枝优化时间复杂度,若拿到的元素和已经超过了target,可以直接废弃当前的组合。

 
参考:
lintcode----k数和II    讲解稍微详细一些
[LintCode] k Sum II [Backtracking]  另一种实现方式
 
 
另一种AC代码:
class Solution {
public:
    /*
     * @param A: an integer array
     * @param k: a postive integer <= length(A)
     * @param target: an integer
     * @return: A list of lists of integer
     */
    vector<vector<int>> kSumII(vector<int> &A, int k, int targer) {
        // write your code here
    vector<vector<int>> result;
    vector<int> cur;
    int sum=0;
    findk(A,k,targer,sum,0,cur,result);
    return result;
    }
    
    void findk(vector<int> &A, int k, int targer,int sum,int ind,vector<int> cur ,vector<vector<int>> &result)
{
    if (cur.size()==k&&sum==targer)
    {
        result.push_back(cur);
        return ;
    }
    if ((int)cur.size()>=k||sum>targer)
    {
        return ;
    }

    for (int i=ind;i<(int)A.size();i++)
    {
        cur.push_back(A[i]);
        findk(A,k,targer,sum+A[i],i+1,cur,result);//注意是i+1不是ind+1;
        cur.pop_back();
    }
}
};

 

 

展开阅读全文
ind
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部