c/c++全排列和组合的写法

全排列和组合本质都是DFS(Deapth First Search) 算法的思想。

• 目标

  输出1-3的全排列和组合.

  输出结果：

• 程序

  #include 
  using namespace std;
  
  // 组合
  void dfs(int step, int goal, int cnt);
  // 排列
  void dfs(int goal, int step);
  
  void dfs2(int step, int goal, int cnt);
  
  int arr[100];
  bool visited[100];
  int main() {
      memset(arr, 0, sizeof(arr));
      std::cout << "Hello, World!" << std::endl;
      dfs(0, 3, 0);
  
  
      cout << "======" << endl;
      memset(visited, 0, sizeof(visited));
      dfs(3, 0);
      return 0;
  }
  
  
  void dfs(int step, int goal, int cnt){
      if (step == goal) {
          if (cnt == 0) {
              cout << "null" << endl;
              return;
          }
          for(int i = 0; i < cnt; i++) {
              cout << arr[i] << " ";
          }
          cout << endl;
          return;
      }
      dfs(step + 1, goal, cnt);
      arr[cnt] = step + 1;
      dfs(step + 1, goal, cnt + 1);
      return;
  }
  
  void dfs(int goal, int step) {
      if(step == goal) {
          for (int i = 0; i < goal; i++) {
              cout << arr[i] << " ";
          }
          cout << endl;
          return;
      }
  
      for(int i = 0; i < goal; i++) {
          if(visited[i]) {
              continue;
          }
          visited[i] =  true;
          arr[step] = i + 1;
          dfs(goal, step + 1);
          visited[i] = false;
      }
  }