找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1945|回复: 4
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【Combination Sum II】-【刷题第一弹2014】

[复制链接]

14

主题

9

精华

373

积分

高级会员

Rank: 3Rank: 3

积分
373
发表于 10-22-2014 11:59 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:25 AM 编辑

快速通道:oj.leetcode.com/problems/combination-sum-ii/


题目:





建议的回复格式:(如果大家有更好的格式可以补充哦)
思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)


=========点击传送门查看所有题目哟========
                            汇总贴 传送门
==================================

思路:这个问题因为要举出所有例子,我就选用了递归+brute-force search

代码:
[code]public class Solution {
    public List> combinationSum2(int[] num, int target) {
        List> ret = new ArrayList>();
        Arrays.sort(num);
        List tmp = new ArrayList();
        combine(ret, num, 0, target, tmp);
        return ret;
    }
    public void combine(List> ret, int[] num, int start, int target, List tmp) {
        if(target==0) {
            List cur = new ArrayList();
            cur.addAll(tmp);
            ret.add(cur);
            return;
        }
        for (int i=start; i             if(i>start && num【i】==num[i-1])
                continue;
            if(target>=num【i】) {
                tmp.add(num【i】);
                combine(ret, num, i+1, target-num【i】, tmp);
                tmp.remove(tmp.size()-1);
            }
        }
    }
}[/code]

复杂度:O(n!)

本帖被以下淘专辑推荐:

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 12-4-2014 07:41 PM | 显示全部楼层
来个c++的,本题是回溯、递归,dfs,剪枝的组合,这些都有涉及,难点和易错点都在剪枝,还有容易出错的地方是在当前层内的循环体末尾,应当将解法复原
  1. class Solution {
  2. public:
  3.     vector<vector<int> > combinationSum2(vector<int> &num, int target) {
  4.         sort(num.begin(), num.end());
  5.         vector<vector<int> > sets;
  6.         vector<int> set;
  7.         combinationSum2Dfs(0, num, set, sets, target);
  8.         return sets;
  9.     }
  10.    
  11.     void combinationSum2Dfs(int start, vector<int> &num, vector<int> &set, vector<vector<int> > &sets, int target){
  12.         if(target < 0) return;
  13.         if(target == 0){
  14.             sets.push_back(set);
  15.             return;
  16.         }
  17.         
  18.         for(int i = start; i < num.size(); i++){
  19.             if(i > start && num[i] == num[i - 1]) continue;
  20.             set.push_back(num[i]);
  21.             combinationSum2Dfs(i + 1, num, set, sets, target - num[i]);
  22.             set.pop_back();
  23.         }
  24.     }
  25. };
复制代码
回复 支持 反对

使用道具 举报

14

主题

9

精华

373

积分

高级会员

Rank: 3Rank: 3

积分
373
 楼主| 发表于 12-5-2014 07:31 PM | 显示全部楼层
wenyuanhust 发表于 12-4-2014 07:41 PM
来个c++的,本题是回溯、递归,dfs,剪枝的组合,这些都有涉及,难点和易错点都在剪枝,还有容易出错的地方 ...

赞!总结得很好
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表