美文网首页
dart实现回溯解决leetcode39、40、46、47、78

dart实现回溯解决leetcode39、40、46、47、78

作者: 锦鲤跃龙 | 来源:发表于2020-11-26 16:42 被阅读0次

    [toc]

    1.leetcode 39

    1.1题目要求和地址

    https://leetcode-cn.com/problems/combination-sum/

    1.2代码

    ///
/// Author: 1254463047@qq.com
/// Date: 2020-11-23 08:44:26
/// FilePath: /algorithm/leetCode/backtrack/_003_39_组合总和.dart
/// Description: https://leetcode-cn.com/problems/combination-sum/
/// 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

// candidates 中的数字可以无限制重复被选取。

// 说明：

// 所有数字（包括 target）都是正整数。
// 解集不能包含重复的组合。

///
class Solution {
  List<List<int>> res; //结果
  List<int> way; //可以成功的一个方法
  List<List<int>> combinationSum(List<int> candidates, int target) {
    res = List();
    way = List();
    dfs(candidates, target, 0);
    return res;
  }

  dfs(List<int> candidates, int target, int begin) {
    int len = candidates.length;
    if (target == 0) {
      res.add(List.from(way));
      return;
    }
    if (target < 0) {
      return;
    }
     // 重点理解这里从 begin 开始搜索的语意
    for (var i = begin; i < len; i++) {
      way.add(candidates[i]);
      print('递归前==$way');
       // 注意：由于每一个元素可以重复使用，下一轮搜索的起点依然是 i，这里非常容易弄错
      dfs(candidates, target - candidates[i], i);
      //回溯 恢复现场
      way.removeLast();
      print('递归后==$way');
    }
  }
}

main(List<String> args) {
  List<int> candidates = [2, 3, 6, 7];
  int target = 7;
  Solution s = Solution();
  print(s.combinationSum(candidates, target));
}

    2.leetcode 40

    2.1题目要求和地址

    https://leetcode-cn.com/problems/combination-sum-ii/

    2.2代码

    
class Solution {
 List<List<int>> res; //结果
  List<int> way; //可以成功的一个方法
  List<List<int>> combinationSum2(List<int> candidates, int target) {
    res = List();
    way = List();
    candidates.sort();
    dfs(candidates, target, 0);
    return res;
  }

  dfs(List<int> candidates, int target, int begin) {
    int len = candidates.length;
    if (target == 0) {
      res.add(List.from(way));
      return;
    }
    if (target < 0) {
      return;
    }
     // 重点理解这里从 begin 开始搜索的语意
    for (var i = begin; i < len; i++) {
      if (target - candidates[i]<0) continue;
      if (i>begin && candidates[i] == candidates[i-1]) continue;
      way.add(candidates[i]);
      print('递归前==$way');
      dfs(candidates, target - candidates[i], i+1);
      //回溯 恢复现场
      way.removeLast();
      print('递归后==$way');
    }
  }
}

main(List<String> args) {
  List<int> candidates = [10,1,2,7,6,1,5];
  int target = 8;
  Solution s = Solution();
  print(s.combinationSum2(candidates, target));
}

    直接结果

    递归前==[1]
递归前==[1, 1]
递归前==[1, 1, 2]
递归后==[1, 1]
递归前==[1, 1, 5]
递归后==[1, 1]
递归前==[1, 1, 6]
递归后==[1, 1]
递归后==[1]
递归前==[1, 2]
递归前==[1, 2, 5]
递归后==[1, 2]
递归后==[1]
递归前==[1, 5]
递归后==[1]
递归前==[1, 6]
递归后==[1]
递归前==[1, 7]
递归后==[1]
递归后==[]
递归前==[2]
递归前==[2, 5]
递归后==[2]
递归前==[2, 6]
递归后==[2]
递归后==[]
递归前==[5]
递归后==[]
递归前==[6]
递归后==[]
递归前==[7]
递归后==[]
[[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]
Exited

    3.leetcode 46

    3.1题目要求和地址

    https://leetcode-cn.com/problems/permutations/

    3.2代码

    
class Solution {
  List<List<int>> res; //最后的结果
  List<bool> used; //已经用到的
  List<int> path; //记录成功的一条
  List<List<int>> permute(List<int> nums) {
    int len = nums.length;
    res = new List();
    if (len == 0) {
      return res;
    }
    used = List(len);
    path = List<int>();
    dfs(nums, 0);
    return res;
  }

  void dfs(
    List<int> nums,
    int depth,
  ) {
    int len = nums.length;
    if (depth == len) {
      res.add(List.from(path)); //因为是指针传递，所以复制一份出来
      return;
    }
    for (int i = 0; i < len; i++) {
      if (used[i] != true) {
        path.add(nums[i]);
        used[i] = true;
        // print('递归之前 =>$path');
        dfs(nums, depth + 1);
        //回溯 回复现场
        used[i] = false;
        path.removeLast();
        // print('递归之后 i=$i =>$path');
      }
    }
  }
}

    验证

    main(List<String> args) {
  List<int> nums = [1, 2, 3];
  Solution s = Solution();
  print(s.permute(nums));
}

    结果

    [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

    3.3 复杂度分析

    回溯算法由于其遍历的特点，时间复杂度一般都比较高，有些问题分析起来很复杂。一些回溯算法解决的问题，剪枝剪得好的话，复杂度会降得很低，因此分析最坏时间复杂度的意义也不是很大。但还是视情况而定。

    • 时间复杂度：O(n*n!)
    • 空间复杂度 O(n*n!)

    时间复杂度分析

    • 在第 1 层，结点个数为 N个数选 1 个的排列
    • 在第 2 层，结点个数为 N个数选 2 个的排列
      所以：非叶子节点个数
      1+\sideset{}{^1_{n}}A +\sideset{}{^2_{n}}A +\sideset{}{^3_{n}}A +... +\sideset{}{^{n-1}_{n}}A
      = 1+n!/(n-1)! +n!/(n-2)! +n!/(n-3)! +... +n!

    因为 n!/(n-1)! +n!/(n-2)! +n!/(n-3)! +... +n!
    = n!*(1/(n-1)! +1/(n-2)! +1/(n-3)! +... +1)
    <= n!*(+1/2 +1/4 +1/8 +... +1/(2^n-1))<2N!

    将常规系数2视为1，每个内部循环N次，故非叶子时间复杂度为O(n*n!)

    4.leetcode 47

    4.1题目要求和地址

    https://leetcode-cn.com/problems/permutations-ii/

    4.2代码

    ///
/// Author: 1254463047@qq.com
/// Date: 2020-11-22 21:12:28
/// FilePath: /algorithm/leetCode/backtrack/003_47_全排列.dart
/// Description: https://leetcode-cn.com/problems/permutations/
///给定一个 没有重复 数字的序列，返回其所有可能的全排列。


class Solution {
  List<List<int>> res; //最后的结果
  List<bool> used; //已经用到的
  List<int> path; //记录成功的一条

  List<List<int>> permute(List<int> nums) {
    int len = nums.length;
    res = new List();
    if (len == 0) {
      return res;
    }
    nums.sort();
    used = List(len);
    path = List<int>();
    dfs(nums, 0);
    return res;
  }

  void dfs(
    List<int> nums,
    int depth,
  ) {
    int len = nums.length;
    if (depth == len) {
      List<int> pathcopy = List.from(path);
      res.add(pathcopy); //因为是指针传递，所以复制一份出来
      return;
    }
    for (int i = 0; i < len; i++) {
      if (used[i] == true) continue;
      // 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义
      // 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择
      if (i > 0 && nums[i] == nums[i - 1] && used[i - 1]!=true) {
        continue;
      }

      path.add(nums[i]);
      used[i] = true;
      print('递归之前 =>$path');
      dfs(nums, depth + 1);
      //回溯 回复现场
      used[i] = false;
      path.removeLast();
      print('递归之后 i=$i =>$path');

    }
  }
}

main(List<String> args) {
  List<int> nums = [1, 1, 3];
  Solution s = Solution();
  print(s.permute(nums));
}

    5.leetcode 78

    5.1题目要求和地址

    https://leetcode-cn.com/problems/subsets/

    5.2代码

    ///
/// Author: 1254463047@qq.com
/// Date: 2020-11-23 17:46:07
/// FilePath: /algorithm/leetCode/backtrack/_003_78_子集.dart
/// Description: https://leetcode-cn.com/problems/subsets/
/// 获取子集问题:回溯解决

class Solution {
  List<List<int>> res; //返回的结果
  List<int> way; //可以成功的一个方法
  List<bool> used; //已经使用过的
  ///
  /// Author: liyanjun
  /// description: 给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
  /// 说明：解集不能包含重复的子集。
  ///
  List<List<int>> subsets(List<int> nums) {
    res = List();
    if (nums == null) {
      return res;
    }
    way = [];
    used = List(nums.length);
    _dfs(nums, 0);
    return res;
  }

  _dfs(List<int> nums, int begin) {
    int len = nums.length;
    res.add(List.from(way));
    if (begin == len) {
      return;
    }
    for (int i = begin; i < len; i++) {
      if (used[i] == true) continue;//剪枝
      way.add(nums[i]);
      used[i] = true;
      //print('递归前==>$way');
      _dfs(nums, i + 1);//从下一位开始计算
      way.removeLast();
      used[i] = false;
      //print('递归后==>$way');
    }
  }
}

main(List<String> args) {
  List<int> nums = [1, 2, 3];
  Solution s = Solution();
  print(s.subsets(nums));
}

    验证

    main(List<String> args) {
  List<int> nums = [1, 2, 3];
  Solution s = Solution();
  print(s.subsets(nums));
}

    输出

    [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

    6.leetcode 90

    6.1题目要求和地址

    https://leetcode-cn.com/problems/subsets-ii/submissions/

    6.2代码

    
class Solution {
  List<List<int>> res; //返回的结果
  List<int> way; //可以成功的一个方法
  List<bool> used; //已经使用过的
  ///
  /// Author: liyanjun
  /// description: 给定一组含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
  /// 说明：解集不能包含重复的子集。
  ///
  List<List<int>> subsets(List<int> nums) {
    res = List();
    if (nums == null) {
      return res;
    }
    way = [];
    used = List(nums.length);
    nums.sort();
    _dfs(nums, 0);
    return res;
  }

  _dfs(List<int> nums, int begin) {
    int len = nums.length;
    res.add(List.from(way));
    if (begin == len) {
      return;
    }
    for (int i = begin; i < len; i++) {
      if (used[i] == true) continue;//剪枝
      if( i>begin && nums[i] == nums[i-1]) continue;
      way.add(nums[i]);
      used[i] = true;
      //print('递归前==>$way'); 
      _dfs(nums, i + 1);//从下一位开始计算
      way.removeLast();
      used[i] = false;
     // print('递归后==>$way');
    }
  }
}

main(List<String> args) {
  List<int> nums = [1, 2, 2];
  Solution s = Solution();
  print(s.subsets(nums));
}

    运行结果

    [[], [1], [1, 2], [1, 2, 2], [2], [2, 2]]

    相关文章

      网友评论

          本文标题：dart实现回溯解决leetcode39、40、46、47、78

          本文链接：https://www.haomeiwen.com/subject/oypbiktx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|dart实现回溯解决leetcode39、40、46、47、78|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！