找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 4651|回复: 7
收起左侧

[米群网刷题小分队] [LeetCode] BackTracking 题目

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-9-2014 12:47 AM | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 MengMa 于 12-12-2014 08:13 PM 编辑

Combination Sum I
Backtracking.
时间和空间都是指数级的。
  1. public ArrayList<ArrayList<Integer>> combinationSum(int[] candidates, int target) {
  2.         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  3.         if(candidates == null || candidates.length == 0) return res;
  4.         Arrays.sort(candidates);
  5.         helper(res, new ArrayList<Integer>(), 0, target, candidates);
  6.         return res;
  7.     }
  8.     //backtracking
  9.     private void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, int start, int target, int[] candidates)
  10.     {
  11.         if(target < 0) return;
  12.         if(target == 0)
  13.         {
  14.             res.add(new ArrayList<Integer>(tmp));
  15.             return;
  16.         }
  17.         for(int i = start; i < candidates.length; i++)
  18.         {
  19.             if(i > 0 && candidates【i】 == candidates[i - 1]) continue;
  20.             tmp.add(candidates【i】);
  21.             helper(res, tmp, i, target - candidates【i】, candidates); // if we cannot use, we do i + 1;
  22.             tmp.remove(tmp.size() - 1);
  23.         }
  24.     }
复制代码
Combination Sum II, 单纯的把Start 从 i 改成 i+ 1没能AC。。等到时候再想想。

本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-9-2014 08:42 PM | 显示全部楼层
本帖最后由 MengMa 于 12-10-2014 02:49 PM 编辑

Combination Sum II

思路和combination sum I 一样。
区别一个是i> start, 而不是 i > 0 因为咱们已经用过的元素不能再用了。且helper() 里面是i + 1。

  1. public ArrayList<ArrayList<Integer>> combinationSum2(int[] candidates, int target) {
  2.         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
  3.         if(candidates == null || candidates.length == 0) return res;
  4.         Arrays.sort(candidates);
  5.         helper(res, new ArrayList<Integer>(), 0, target, candidates);
  6.         return res;
  7.     }
  8.     //backtracking
  9.     private void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, int start, int target, int[] candidates)
  10.     {
  11.         if(target < 0) return;
  12.         if(target == 0)
  13.         {
  14.             res.add(new ArrayList<Integer>(tmp));
  15.             return;
  16.         }
  17.         for(int i = start; i < candidates.length; i++)
  18.         {
  19.             if(i > start && candidates【i】 == candidates[i - 1]) continue;  // i > start, not i > 0
  20.             tmp.add(candidates【i】);
  21.             helper(res, tmp, i + 1, target - candidates【i】, candidates); // if we cannot use, we do i + 1;
  22.             tmp.remove(tmp.size() - 1);
  23.         }
  24.     }
复制代码


90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-12-2014 08:11 PM | 显示全部楼层
Combinations


backtracking
  1. public class Solution {
  2.     public ArrayList<ArrayList<Integer>> combine(int n, int k) {
  3.         ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>> ();
  4.         if(n < 0 || k < 0 || n < k) return res;
  5.         helper(res, new ArrayList<Integer>(), k, n, 1);
  6.         return res;
  7.     }
  8.     private void helper(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> tmp, int k, int n, int start)
  9.     {
  10.         if(tmp.size() == k) //termination
  11.         {
  12.             res.add(new ArrayList<Integer>(tmp));
  13.             return;
  14.         }
  15.         for(int i = start; i <= n; i++ )
  16.         {
  17.             tmp.add(i);
  18.             helper(res, tmp, k, n, i + 1);
  19.             tmp.remove(tmp.size() - 1);
  20.         }
  21.     }
  22. }
复制代码


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

本版积分规则

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