DFS（搜索）

[Ir1d]

https://oi-wiki.org/search/dfs/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[32thirtytwo]

请问a是什么意思

[tsaihaojiang]

a就是答案

[EdwardKemway]

第一个案例当n < 0时return就可了吧

[WWWzq-01]

@32thirtytwo
请问a是什么意思
ai-1,前一个正整数

[WWWzq-01]

@EdwardKemway
第一个案例当n < 0时return就可了吧

你的意思是加一个当n<0时return吗?我觉得应该要加,否则要等i大于m才停止,有些不必要的递归

[lplalbert]

题目中说要不同的正整数，按后面的两个代码来理解应该把 不同的 三个字去了吧

[ksyx]

第一个问题使最后一位直接由减法获得，然后判断一下大小，能省下一个维度的复杂度

方便的话可以来个 pr

[Aumble-Traumer]

好！

[henry20100605]

棒极了！！！

[BreakingLead]

笑死, 直接模板元编程套for

[Kirigiri123]

支持

[hekpwho]

列题一都说了三个不同的正整数，怎么后面还来了个大于等于

[xsy2013]

对学弟很有帮助

[zhangjialin996]

public class DFS {
  /* 满足长度为m，且a1< ... < am的数组，ai为正整数，数组和为n的方案总数
  * n：表示当前还差多少
  * curLen：表示当前长度
  * preValue：表示数组当前最后一个位置的值
  */

  int planNum;
  int MAX_LEN;
  int[] arr = new int[1001];

  public void dfs(int n, int curLen, int preValue){
    if(n == 0 && curLen == MAX_LEN) {
      planNum++;
      printArr(curLen);
    }
    if(curLen < MAX_LEN){
      for(int j = preValue + 1; j <= n; j++){
        if(n - j < 0) return ;
        arr[curLen] = j;
        dfs(n - j, curLen + 1 , j);
      }
    }
  }

  public void printArr(int len){
    for(int i = 0; i < len; i++){
      System.out.print(arr[i] + "===");
    }
    System.out.println();
  }

  public static void main(String[] args){
    DFS solution = new DFS();
    solution.MAX_LEN = 3;
    solution.dfs(20, 0, 0);
    System.out.println(solution.planNum);
  }
}

[zhangjialin996]

全排列问题

import java.util.*;

public class P1706 {
  public static void main(String... args){
    Scanner in = new Scanner(System.in);
    int N = in.nextInt();
    int[] store = new int[N];
    dfs(store, 0, N);
  }

  public static void dfs(int[] nums, int curLen, int neededLen){
    if(curLen == neededLen) printRes(nums);

    for(int i = 1; i <= neededLen; i++){
      if(!ifNotIn(nums, curLen, i)) continue ;
      nums[curLen] = i;
      dfs(nums, curLen + 1, neededLen);
    }
  }

  public static void printRes(int[] res){
    for(int element : res){
      System.out.print("     " + element);
    }
    System.out.println();
  }

  public static boolean ifNotIn(int[] nums, int len, int checkedNum){
    for(int i = 0; i < len; i++){
      if(nums[i] == checkedNum) return false;
    }
    return true;
  }
}

[ATION001]

C++ 自带一个全排列函数：next_permutation。

[joker-frank]

public class DFS {
/* 满足长度为m，且a1< ... < am的数组，ai为正整数，数组和为n的方案总数

• n：表示当前还差多少
• curLen：表示当前长度
• preValue：表示数组当前最后一个位置的值
  */

int planNum;
int MAX_LEN;
int[] arr = new int[1001];

public void dfs(int n, int curLen, int preValue){
if(n == 0 && curLen == MAX_LEN) {
planNum++;
printArr(curLen);
}
if(curLen < MAX_LEN){
for(int j = preValue + 1; j <= n; j++){
if(n - j < 0) return ;
arr[curLen] = j;
dfs(n - j, curLen + 1 , j);
}
}
}

public void printArr(int len){
for(int i = 0; i < len; i++){
System.out.print(arr[i] + "===");
}
System.out.println();
}

public static void main(String[] args){
DFS solution = new DFS();
solution.MAX_LEN = 3;
solution.dfs(20, 0, 0);
System.out.println(solution.planNum);
}
}

[joker-frank]

···
public class DFS {
/* 满足长度为m，且a1< ... < am的数组，ai为正整数，数组和为n的方案总数

• n：表示当前还差多少
• curLen：表示当前长度
• preValue：表示数组当前最后一个位置的值
  */

int planNum;
int MAX_LEN;
int[] arr = new int[1001];

public void dfs(int n, int curLen, int preValue){
if(n == 0 && curLen == MAX_LEN) {
planNum++;
printArr(curLen);
}
if(curLen < MAX_LEN){
for(int j = preValue + 1; j <= n; j++){
if(n - j < 0) return ;
arr[curLen] = j;
dfs(n - j, curLen + 1 , j);
}
}
}

public void printArr(int len){
for(int i = 0; i < len; i++){
System.out.print(arr[i] + "===");
}
System.out.println();
}

public static void main(String[] args){
DFS solution = new DFS();
solution.MAX_LEN = 3;
solution.dfs(20, 0, 0);
System.out.println(solution.planNum);
}
}

[Tempest225]

def dfs(n,i,arr):#递归寻找,n表示每次被拆分后所剩的数，i表示拆分层数,a表示每次拆分的初始值
if i==n:
for num in arr:
print(" {}".format(num),end="")
print()
for j in range(i,n):
arr[i],arr[j]=arr[j],arr[i]
dfs(n,i+1,arr)
arr[i],arr[j]=arr[j],arr[i]
n=int(input())#n输入
arr=[i for i in range(1,n+1)]#n的全排列数组存储空间
arr_change=[]
dfs(n,0,arr)
我理解不了，为什么这个在洛谷上面是错的，换位也能实现全排列啊

[muenzhang]

本页面是不是少了点习题（