dfs回溯

今天药忘吃喽~ 2022-12-13 04:35 128阅读 0赞

### dfs回溯 ###

遍历所有元素，输出所有可能的组合可以使用dfs回溯  
这里用输出1到3有多少种组合作为例子  
代码

public class DFS { 
    	static String s = "";
    	public static void main(String[] args) { 
    		dfs("" , 1);
    	}
    	public static void dfs(String s , int cyq) { 
    		if(cyq > 3) { 
    			System.out.println(s);
    			return;
    		}
    		for(int i = 1 ; i <= 3 ; i++) { 
    			dfs(s + i , cyq + 1);
    		}
    	}
    }

输入：

111	112
    113	121
    122	123
    131	132
    133	211
    212	213
    221	222
    223	231
    232	233
    311	312
    313	321
    322	323
    331	332
    333

如果需要不重复使用元素，需要加入`vis`数组来记录是否使用过该位置的元素，同时在dfs遍历时用`!vis[i]`判断并设置为`true`

public class DFS { 
    	static String s = "";
    	static boolean vis[]=new boolean[4];
    	public static void main(String[] args) { 
    		dfs("" , 1);
    	}
    	public static void dfs(String s , int cyq) { 
    		if(cyq > 3) { 
    			System.out.println(s);
    			return;
    		}
    		for(int i = 1 ; i <= 3 ; i++) { 
    			if(!vis[i]) { 
    				vis[i] = true;
    				dfs(s + i , cyq + 1);
    				vis[i] = false;
    			}
    		}
    	}
    }

输出

123
    132
    213
    231
    312
    321

发表评论取消回复

表情：

评论列表（有 0 条评论，128人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode-回溯问题总结（DFS）

文章目录 1.DFS 2. for+递归解决通用问题 3. 回溯问题减枝加速 4. 组合&排序&子集组合总和(回溯)（深度优先遍历D

比眉伴天荒/ 2023年03月13日 06:18/ 0 赞/ 15 阅读

相关 dfs回溯

dfs回溯遍历所有元素，输出所有可能的组合可以使用dfs回溯这里用输出1到3有多少种组合作为例子代码 public class DFS {

今天药忘吃喽~/ 2022年12月13日 04:35/ 0 赞/ 129 阅读

相关 (模板)N 皇后问题(DFS 回溯剪枝)

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![0242897a3a17b699ec318bfcbeb17e3b.png

￡神魔★判官ぃ/ 2022年12月07日 15:11/ 0 赞/ 151 阅读

相关全排列——回溯算法+dfs

leetcode.46.全排列——回溯算法+dfs 给定一个没有重复数字的序列，返回其所有可能的全排列。示例: 输入: [1,2,3] 输出:

骑猪看日落/ 2022年12月04日 15:56/ 0 赞/ 170 阅读

相关 hdoj 1312 Red and Black【dfs，回溯】

Red and Black Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (

我不是女神ヾ/ 2022年08月04日 12:35/ 0 赞/ 88 阅读

相关 ACM dfs回溯法 Prime Ring Problem

滴，集训第二天打卡。今天是紫书第七章训练+约瑟夫问题。约瑟夫问题就是一个公式可以解决的事情~~ 基本套路就是： include <stdio.h>

不念不忘少年蓝@/ 2022年06月12日 07:07/ 0 赞/ 151 阅读

相关 CodeForces - 633C(字典树+dfs回溯)

C. Spy Syndrome 2 time limit per test 2 seconds memory limit per test 256 megabytes

缺乏、安全感/ 2022年05月28日 13:05/ 0 赞/ 139 阅读

相关 [leetcode] 51 N皇后（路径打印＋DFS+回溯）

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。 ![format_png][] 上图为 8 皇后问题的一种解法。给定一

分手后的思念是犯贱/ 2021年10月03日 02:34/ 0 赞/ 289 阅读

相关 leetcode：79. 单词搜索（java 回溯dfs）

package LeetCode; / 79. 单词搜索给定一个二维网格和一个单词，找出该单词是否存在于网格中。单

Myth丶恋晨/ 2021年09月28日 07:14/ 0 赞/ 278 阅读

相关 ✔[77]组合（回溯，DFS）

//给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合。 // // 示例: // // 输入: n = 4, k = 2 //输出:

约定不等于承诺〃/ 2021年06月22日 15:38/ 0 赞/ 451 阅读