dfs

标签：used nums int dfs candidates new path

1.1 排列组合问题

排列组合问题还得是卡子哥讲的通透

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

组合与排列

组合问题是从给定的元素集合中选取若干元素，不考虑元素的顺序，求子集的问题；而排列问题是从给定的元素集合中选取若干元素，考虑元素的顺序，求不同排列的问题。

组合问题：假设有集合 {A, B, C}，我们想要从中选择两个元素，不考虑顺序。组合问题涉及选择的元素集合，如 {A, B}、{A, C}、{B, C}，而不考虑元素的排列顺序。例如，{A, B} 和 {B, A} 视为相同的组合。

排列问题：同样假设有集合 {A, B, C}，我们想要从中选择两个元素，考虑元素的排列顺序。排列问题涉及选择的元素排列，如 (A, B)、(A, C)、(B, A)、(B, C) 等，每个排列视为不同的选择，因为元素的顺序不同。

1.1.1 组合问题

力扣 216.组合总和III

思路：回溯

终止条件：sum == n && path.size == k

循环条件：每种组合中不存在重复的数字 => i +1

处理节点：sum+=i ; path.add(i)

递归：backTracking(i+1,sum,k)

剪枝：因为是[1,2,3...9]的递增有序集和，所以剪枝操作放到for循环判断更有效。剪枝判断显然是 sum > n

回溯：sum-=i; path.remove(path.size()-1);

public class Solution {
    /*
     * //使用static关键字声明res和path作为类的静态成员会导致在算法执行过程中出现问题，
     * // 特别是当涉及到多个测试用例或多个Solution类的实例时。
     * static List<List<Integer>> res = new ArrayList<>();
     * static List<Integer> path = new LinkedList<>();
     */
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backTracking(k, n, 1, 0);
        return res;
    }

    private void backTracking(int k, int n, int startIndex, int sum) {
        if (sum > n)
            return;

        if (path.size() > k)
            return;

        if (sum == n && path.size() == k) {
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i <= 9; i++) {
            path.add(i);
            sum += i;
            backTracking(k, n, i + 1, sum);
            sum -= i;
            path.remove(path.size() - 1);
        }
    }

}

组合总和II

与上一题区别在于：

本题数组candidates的元素是有重复的，而上一题是无重复元素的数组candidates

最后本题和上一题要求一样，解集不能包含重复的组合。上一题因为没有重复元素，只需要保证startIndex = i+1就不会出现重复组合

但是这题的集合（数组candidates）有重复元素，但还不能有重复的组合。

对于这道问题，由于数组 candidates 中的元素可能重复，但解集中不能包含重复的组合，我们可以采用以下策略：

排序数组：首先对数组 candidates 进行排序，这样相同的元素会相邻排列。
回溯法避免重复：在回溯过程中，为了避免产生重复的组合，我们可以在每一层递归中跳过相同的元素，以确保不会重复选择相同的组合。这步操作对应卡哥说的树层去重操作.

class Solution {
  List<List<Integer>> res = new ArrayList<>();
  LinkedList<Integer> path = new LinkedList<>();
  int sum = 0;
  
  public List<List<Integer>> combinationSum2( int[] candidates, int target ) {
    //为了将重复的数字都放到一起，所以先进行排序
    Arrays.sort( candidates );
    backTracking( candidates, target, 0 );
    return res;
  }
  
  private void backTracking( int[] candidates, int target, int start ) {
    if ( sum == target ) {
      res.add( new ArrayList<>( path ) );
      return;
    }
    for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ ) {
      //正确剔除重复解的办法
      //跳过同一树层使用过的元素
      if ( i > start && candidates[i] == candidates[i - 1] ) {
        continue;
      }

      sum += candidates[i];
      path.add( candidates[i] );
      // i+1 代表当前组内元素只选取一次
      backTracking( candidates, target, i + 1 );

      int temp = path.getLast();
      sum -= temp;
      path.removeLast();
    }
  }
}

1.1.2 排列问题

47.全排列 II

排列问题去重

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    boolean[] used;
    public List<List<Integer>> permuteUnique(int[] nums) {
        used = new boolean[nums.length];
        Arrays.fill(used,false);
        Arrays.sort(nums);
        backTracking(nums);
        return res;
    }
    public void backTracking(int[] nums){
        if(path.size() == nums.length){
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0 ; i < nums.length ; i++){
            if(i > 0 && nums[i-1] == nums[i] && used[i-1] == false){
                continue;
            }
            if(used[i] == false){
                used[i] = true;
                path.add(nums[i]);
                backTracking(nums);
                used[i] = false;
                path.removeLast();
            }
        }

    }
}

LeetCode 996. 正方形数组的数目

题解：全排列+排序去重+相邻元素特判

package com.coedes.dfs.likou996;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @description：https://leetcode.cn/problems/number-of-squareful-arrays/
 * @author： wenLiu
 * @create： 2024/5/9 23:23
 */
public class Solution {

    int cnt = 0;

    public int numSquarefulPerms(int[] nums) {

        int n = nums.length;
        Arrays.sort(nums);
        boolean[] used = new boolean[n + 1];
        Arrays.fill(used, false);
        List<Integer> path = new LinkedList<>();
        dfs(0,nums, used, path);
        return cnt;
    }

    private void dfs(int i, int[] nums, boolean[] used, List<Integer> path) {
        if (i == nums.length) {
            cnt++;
            return;
        }
        for (int j = 0; j < nums.length; j++) {
            if (used[j]) continue;
            // 去重
            if (j > 0 && nums[j - 1] == nums[j] && !used[j-1]) continue;
            // 相邻元素和是否为完全平方数判断
            if (path.size() > 0 && !check(path.get(path.size() - 1) + nums[j])) continue;
            used[j] = true;
            path.add(nums[j]);
            dfs(i+1, nums, used, path);
            used[j] = false;
            path.remove(path.size() - 1);
        }
    }

    private boolean check(int i) {
        int sqrOfi = (int) Math.sqrt(i);
        return sqrOfi * sqrOfi == i;
    }
}

acwing 94. 递归实现排列型枚举

题解：通过dfs方式求排列，本质还是回溯

https://www.acwing.com/solution/content/44647/

import java.util.Scanner;

public class Main {
    static final int N = 10;
    static int[] nums = new int[N];  // 存储排列的数组
    static boolean[] st = new boolean[N];  // 标记数组，表示每个数字是否已经被使用过
    static int n;  // 排列的长度

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        dfs(1);  // 从第一个位置开始深度优先搜索
    }

    static void dfs(int u) {
        // 如果已经排列完所有的数字，输出结果
        if (u > n) {
            for (int i = 1; i <= n; i++)
                System.out.print(nums[i] + " ");
            System.out.println();
            return;
        }
        // 枚举可选的数字
        for (int i = 1; i <= n; i++) {
            // 如果数字未被使用过，选择它并继续搜索
            if (!st[i]) {
                nums[u] = i;  // 将数字 i 放入当前位置
                st[i] = true;  // 标记数字 i 已被使用
                dfs(u + 1);  // 继续搜索下一个位置
                st[i] = false;  // 恢复状态，回溯
            }
        }
    }
}

2023柠檬微趣-排队

题目描述：

问题描述：给定了 m 位学生，每位学生有唯一的编号 1 到 m。现在需要找出所有学生排队的方案，并按照字典序升序排序。
问题求解：需要找出所有可能的学生排队方案，这些方案按照字典序排序，然后输出第 n 个排队方案。

输入描述

输入第一行为一个整数 m ，表示学生和位置数。（1≤m≤10 ）

输入第二行为一个整数 n ，表示排列方案序号。（ 1≤n≤10^9 ）

输出描述

若存在第 n 个方案，输出作为方案，数组间元素用空格隔开。

若不存在该方案，输出 −1。

eg1:
input:
4
5

output:
1 4 2 3

eg2:
input:
3
7

output:
-1

　思路：m个数全排列+计数

　　题目可以转化为： 打印m个数字的全排列中的第n个排列

　这道题用卡哥

static List<List<Integer>> res = new ArrayList<>();

static List<Integer> path = new LinkedList<>();
收集答案会爆内存...
以后尽量用数组收集吧...

package com.coedes.dfs.ningmeng2023050604;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;



/**
 * @description：https://codefun2000.com/p/P1280
 * @author： wenLiu
 * @create： 2024/5/9 10:16
 */
public class Main {
    static int cnt = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int m = Integer.parseInt(reader.readLine());
        int n = Integer.parseInt(reader.readLine());

        int[] path = new int[m];

        boolean[] used = new boolean[m+1];
        Arrays.fill(used,false);
　　　　
        int[] f = new int[m + 1];
        f[1] = 1;
        for (int i = 2; i <= m; i++) {
            f[i] = f[i - 1] * i;
        }
　　　　　//m个数全排列最多有m！种 
        if (f[m] < n) {
            System.out.println(-1);
        }else {
            dfs(0,m,n,path,used);
        }
    }

    private static void dfs(int i, int m, int n, int[] path, boolean[] used) {
        if (i == m) {
            cnt++;
            if (cnt==n) {
                for (int i1 : path) {
                    System.out.print(i1+" ");
                }
            }
            return;
        }
        for (int j = 1; j <= m; j++) {
            if (used[j]== true) {
                continue;
            }
            used[j] = true;
            path[i] = j;
            dfs(i+1,m,n,path,used);
            used[j] = false;
        }
    }
}

1.2 子集方式枚举

标签：used,nums,int,dfs,candidates,new,path
From： https://www.cnblogs.com/alohablogs/p/18152907