蓝桥杯算法心得——拼数（排列型回溯dfs）

大家好，我是晴天学长，排列型的dfs，在一些需要暴搜的题中很中很重要，需要的小伙伴可以关注支持一下哦！后续会继续更新的。💪💪💪

---

1) .拼数

---

2) .算法思路

超级递归

1.遍历数组，选中为true
有三层遍历，但都可以交给递归。
2.注意回溯的状态

---

3）.算法步骤

1.创建一个整数变量ans，用于记录拼接数的个数。
2.创建静态整数变量k和整数数组num，用于存储输入的拼接数的要求和数字数组。
3.创建一个HashSet集合set，用于存储所有可能的拼接数。
4.在main方法中，接收输入的整数n和k1，分别表示数字数组的长度和拼接数的要求。
5.将k1赋值给变量k，并创建一个长度为n的整数数组nums，将其赋值给num。
6.使用循环接收数字数组的输入。
7.创建一个布尔数组st，用于标记数字数组中的元素是否已经被访问过。
8.调用dfs方法，传入初始长度0、空字符串s和布尔数组st。
9.在dfs方法中，判断如果当前路径的长度等于拼接数的要求k：
a. 将当前拼接数s添加到集合set中。
b. 返回。
10遍历数字数组num的每个元素：
a. 如果当前元素未被访问：
（1）将当前元素转换为字符串s1。
（2）将当前元素标记为已访问。
（3）将当前元素拼接到拼接数s的末尾。
（4）递归调用dfs方法，传入长度加1、更新后的拼接数s和布尔数组st。
（5）将当前元素标记为未访问，以便后续的回溯。
（6）将拼接数s从末尾删除当前元素的长度，恢复路径状态。
11.输出集合set的大小，即拼接数的个数。

---

4）. 代码实例

package LanQiaoTest.DFS;

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class 拼数 {
    int ans = 0;
    static int k;
    static int[] num;
    static Set<String> set = new HashSet<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k1 = scanner.nextInt();
        k = k1;
        int[] nums = new int[n];
        num = nums;
        //接受数据
        for (int i = 0; i < n; i++) {
            nums[i] = scanner.nextInt();
        }
        boolean[] st = new boolean[n];
        dfs(0, "", st);
        System.out.println(set.size());
    }

    public static void dfs(int length, String s, boolean[] st) {
        //出口
        if (length == k) {
            set.add(s);
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (!st[i]) {
                String s1 = Integer.toString(num[i]);
                st[i] = true;
                s = s + s1;
                dfs(length + 1, s, st);
                st[i] = false;
                s = s.substring(0, s.length() - s1.length());
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

4）.总结

• 怎么排列，怎么回溯。

---

试题链接：