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

[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]]