eclipse leetcode 回溯算法（DFS）

参考大佬：5.6 回溯算法总结 | 算法吧 (suanfa8.com)

题型一：排列、组合、子集相关问题

特别注意：此类题目要分析是否要对数组进行排列！！！！

1.46. 全排列

2.47. 全排列 II

3.好好体会大佬做法**必看** 78. 子集

4.90. 子集 II

5.77. 组合

题型一：排列、组合、子集相关问题

特别注意：此类题目要分析是否要对数组进行排列！！！！

1.46. 全排列

package main;

import java.io.*;

import java.math.*;

import java.util.*;

import javax.swing.text.StyledEditorKit.BoldAction;

public class Main {

//[1,2,3]的全排列

//编写全排列的函数

public ArrayList> solve(int[] nums){

int len=nums.length;

ArrayList> res=new ArrayList<>();//存放所有可能路径的情况

//特判

if(len==0) {

return res;

}

boolean[] used=new boolean[len];//标记遍历的结点是否使用过

ArrayList path=new ArrayList<>(len);//存放一次遍历的路径

dfs(nums, len, 0, used, path, res);

return res;

}

//回溯算法DFS

public void dfs(int[] nums,int len,int depth,//depth:代表问题转换后的层数也代表和着path要填写的元素下标

boolean[] used,ArrayList path,ArrayList> res) {

//当path当中已经完成了从根节点到叶子结点的一次延伸

if(path.size()==len) {

res.add(new ArrayList<>(path));

return;

}

//遍历used数组获取未使用过的结点

for (int i = 0; i < used.length; i++) {

if(!used[i]) {

//将当前结点加入path变量

path.add(nums[i]);

used[i]=true;

//从当前结点再开始DFS

dfs(nums, len, depth+1, used, path, res);

//当前结点DFS完成之后要恢复到原状态

path.remove(path.size()-1);

used[i]=false;

}

public static void main(String[] args) {

Main test=new Main();

int[] nums=new int[] {1,2,3};

ArrayList> ans=test.solve(nums);

System.out.println(ans);

}

2.47. 全排列 II

此题就开始了剪枝！好好体会剪枝如何设置！

// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义

// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择

if(i>0&&nums[i-1]==nums[i]&&!used[i-1]) {

continue;

}

class Solution {

public List> permuteUnique(int[] nums) {

int len=nums.length;

List> res=new ArrayList>();

if(len==0) {

return res;

}

Arrays.sort(nums);

boolean[] used=new boolean[len];

ArrayList path=new ArrayList<>(len);

dfs(nums,len,0,used,path,res);

return res;

}

private void dfs(int[] nums, int len, int depth, boolean[] used, ArrayList path, List> res) {

if(path.size()==len) {

res.add(new ArrayList(path));

return;

}

LOOP:for (int i = 0; i < used.length; i++) {

if(!used[i]) {

// 剪枝条件：i > 0 是为了保证 nums[i - 1] 有意义

// 写 !used[i - 1] 是因为 nums[i - 1] 在深度优先遍历的过程中刚刚被撤销选择

if(i>0&&nums[i-1]==nums[i]&&!used[i-1]) {

continue;

}

path.add(nums[i]);

used[i]=true;

dfs(nums, len, depth+1, used, path, res);

used[i]=false;

path.remove(path.size()-1);

}

3.好好体会大佬做法**必看** 78. 子集

自己思考做法：本题我们首先画出树形图，编写剪枝条件

通过画出树形图我可以看出所剪枝的都是如果当前path的最后一个元素如果大于要新加入则不进行添加continue继续循环。

自己所写代码如下：

class Solution {

public List> subsets(int[] nums) {

int len=nums.length;

List> res=new ArrayList>();

res.add(new ArrayList<>());

if(len==0) return res;

ArrayList path=new ArrayList<>(len);

boolean[] used=new boolean[len];

dfs(nums,len,0,used,path,res);

return res;

}

private void dfs(int[] nums, int len, int depth, boolean[] used, ArrayList path, List> res) {

// TODO Auto-generated method stub

if(path.size()==len) return;

for (int i = 0; i < len; i++) {

if(!used[i]) {

if(path.size()>0) if(path.get(path.size()-1)>nums[i]) continue;

path.add(nums[i]);

res.add(new ArrayList(path));

used[i]=true;

dfs(nums, len, depth+1, used, path, res);

used[i]=false;

path.remove(path.size()-1);

}

大佬则采用了一种更巧妙的方法！！核心如下

import java.util.ArrayList;

import java.util.List;

import java.util.Stack;

public class Solution {

public List> subsets(int[] nums) {

List> res = new ArrayList<>();

int len = nums.length;

if (len == 0) {

return res;

}

Stack stack = new Stack<>();

dfs(nums, 0, len, stack, res);

return res;

}

private void dfs(int[] nums, int index, int len,

Stack stack, List> res) {

if (index == len) {

res.add(new ArrayList<>(stack));

return;

}

// 当前数可选，也可以不选

// 不选，直接进入下一层

dfs(nums, index + 1, len, stack, res);

// 选了有，进入下一层

stack.add(nums[index]);

dfs(nums, index + 1, len, stack, res);

stack.pop();

}

public static void main(String[] args) {

int[] nums = {1, 2, 3};

Solution solution = new Solution();

List> subsets = solution.subsets(nums);

System.out.println(subsets);

}

private void find(int[] nums, int begin, List pre) {

// 没有显式的递归终止

res.add(new ArrayList<>(pre));// 注意：Java 的引用传递机制，这里要 new 一下

for (int i = begin; i < nums.length; i++) {

pre.add(nums[i]);

find(nums, i + 1, pre);

pre.remove(pre.size() - 1);// 组合问题，状态在递归完成后要重置

}

// res.add(new ArrayList<>(pre));放到这里就是后序遍历结果！！

}

import java.util.ArrayList;

import java.util.List;

public class Solution {

private List> res;

private void find(int[] nums, int begin, List pre) {

// 没有显式的递归终止

res.add(new ArrayList<>(pre));// 注意：Java 的引用传递机制，这里要 new 一下

for (int i = begin; i < nums.length; i++) {

pre.add(nums[i]);

find(nums, i + 1, pre);

pre.remove(pre.size() - 1);// 组合问题，状态在递归完成后要重置

}

public List> subsets(int[] nums) {

int len = nums.length;

res = new ArrayList<>();

if (len == 0) {

return res;

}

List pre = new ArrayList<>();

find(nums, 0, pre);

return res;

}

4.90. 子集 II

经过上面的题目的洗礼，我们可以有多种思路拿下此题！

方法一：固定思维：

我们先画出树形图，来观察为什么，以及何时需要剪枝

观察剪枝条件：1.与前一个撤销的值不能再次添加2.不能添加小于当前path最后一个数值的元素

还要额外分析此题是否需要提前对传入的数组进行排序：需要去重所以排序

有了前面的基础轻松拿下！！

class Solution {

public List> subsetsWithDup(int[] nums) {

int len=nums.length;

List> res=new ArrayList>();

Deque path=new ArrayDeque<>(len);

res.add(new ArrayList<>(path));

if(len==0) return res;

Arrays.sort(nums);

boolean[] used=new boolean[len];

dfs(nums,len,0,used,path,res);

return res;

}

private void dfs(int[] nums, int len, int depth, boolean[] used, Deque path, List> res) {

// TODO Auto-generated method stub

if(path.size()==len) return;

for (int i = 0; i < len; i++) {

if(!used[i]) {

if(i>0&&nums[i]==nums[i-1]&&!used[i-1]

||path.size()>0&&path.getLast()>nums[i]) {

continue;

}

path.addLast(nums[i]);

res.add(new ArrayList<>(path));

used[i]=true;

dfs(nums, len, depth+1, used, path, res);

path.removeLast();

used[i]=false;

}

方法二：学习第三题的两种思维的第二种选几个元素然后在进行去掉重复的剪枝即可

同样我们轻松拿下此题！

class Solution {

public List> subsetsWithDup(int[] nums) {

int len=nums.length;

List> res=new ArrayList>();

Deque path=new ArrayDeque<>(len);s

Arrays.sort(nums);

if(len==0) return res;

boolean[] used=new boolean[len];

dfs(nums,len,0,used,path,res);

return res;

}

private void dfs(int[] nums, int len, int begin, boolean[] used, Deque path, List> res) {

res.add(new ArrayList(path));

for (int i = begin; i < len; i++) {

if(!used[i]) {

if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;

path.addLast(nums[i]);

used[i]=true;

dfs(nums, len, i+1, used, path, res);

path.removeLast();

used[i]=false;

}

5.77. 组合

自己思路：

画出树形图：发现就是前面我们所学的结合，只不过将结果集中在了叶子结点，并且这里的输入变量k就是我们要选的元素个数的最大值

我们轻松拿下此题，但是时间方面仍然存在较大的缺陷

class Solution {

public List> combine(int n, int k) {

//先生成数组

int[] nums=new int[n];

int len=n;

for (int i = 0; i < len; i++)

nums[i]=i+1;

List> res=new ArrayList>();

if(len==0) return res;

Deque path=new ArrayDeque(len);

if(len==1) {

path.addLast(nums[0]);

res.add(new ArrayList(path));

return res;

}

dfs(nums,len,0,k,path,res);

return res;

}

private void dfs(int[] nums, int len, int begin, int last, Deque path, List> res) {

// TODO Auto-generated method stub

if(path.size()==last) {//到达所需要的叶子结点

res.add(new ArrayList(path));

return;

}

for (int i = begin; i < nums.length; i++) {

path.addLast(nums[i]);

dfs(nums, len, i+1, last, path, res);

path.removeLast();//回溯

}

大佬做法：进行了很好的优化，可以节省大量时间

移步大佬题解：回溯算法 + 剪枝（Java） - 组合 - 力扣（LeetCode） (leetcode-cn.com)

6.39. 组合总和

此题未得到解决参考了大佬的题解

回溯算法 + 剪枝（回溯经典例题详解） - 组合总和 - 力扣（LeetCode） (leetcode-cn.com)

dfs(candidates, i, target-path.getLast(), path, res);

这句话十分的巧妙，我们下一次的起始位置还是i,因为可能会重复选择，而且整个树的向下推进是通过target-path.getLast();来实现！！！！！！

private void dfs(int[] candidates, int begin, int target, Deque path, List> res) {

// TODO Auto-generated method stub

if(target==0) {

res.add(new ArrayList(path));

return;

}

dfs(candidates, i, target-path.getLast(), path, res);

path.removeLast();

}

7.40. 组合总和 II

根据上一题的基础很快得出代码：

public List> combinationSum2(int[] candidates, int target) {

int len=candidates.length;

List> res=new ArrayList>();

if(len==0) return res;

Arrays.sort(candidates);

boolean[] used=new boolean[len];

Deque path=new ArrayDeque();

dfs(candidates,0,target,used,path,res);

return res;

}

private void dfs(int[] candidates, int begin, int target,boolean[] used, Deque path, List> res) {

// TODO Auto-generated method stub

if(target==0) {

res.add(new ArrayList(path));

return;

}

for (int i =begin; i < candidates.length; i++) {

if(target<0) break;

if(i>0&&candidates[i]==candidates[i-1]&&!used[i-1]) continue;

path.add(candidates[i]);

used[i]=true;

dfs(candidates, i+1, target-path.getLast(),used, path, res);

path.removeLast();

used[i]=false;

}

大佬题解如下： 40. 组合总和 II 题解 - 力扣（LeetCode） (leetcode-cn.com)

文章来源

评论可见，请评论后查看内容，谢谢！！！

您阅读本篇文章共花了：

金钥匙

eclipse leetcode 回溯算法（DFS）

ide JDK环境搭建 2023免费开发工具集成开发环境代码开发技巧 2023 Java程序员必备 Eclipse免费下载安装教程+JDK配置环境搭建教程+Eclipse代码开发使用技巧一站式捆绑服务到底,足够全、足够详细、足够劲爆、简单易学!

java ide pycharm 开发语言下载安装超详细Eclipse 和 JDK教程下载与安装步骤

发表评论取消回复

金钥匙

eclipse leetcode 回溯算法（DFS）

ide JDK环境搭建 2023免费开发工具 集成开发环境 代码开发技巧 2023 Java程序员必备 Eclipse免费下载安装教程+JDK配置环境搭建教程+Eclipse代码开发使用技巧 一站式捆绑服务到底,足够全、足够详细、足够劲爆、简单易学!

java ide pycharm 开发语言 下载安装 超详细Eclipse 和 JDK教程下载与安装步骤

相关文章

发表评论取消回复

ide JDK环境搭建 2023免费开发工具集成开发环境代码开发技巧 2023 Java程序员必备 Eclipse免费下载安装教程+JDK配置环境搭建教程+Eclipse代码开发使用技巧一站式捆绑服务到底,足够全、足够详细、足够劲爆、简单易学!

java ide pycharm 开发语言下载安装超详细Eclipse 和 JDK教程下载与安装步骤