baekjoon 15650:N과 M (2)

baekjoon 15650 N과 M (2)

15650번 N과 M (2)

접근

백트레킹 문제를 좀 풀어보고 싶어서 골랐다.
백트레킹은 완전 탐색의 한 방식이다. 막히면 돌아간다는 의미이다.

코드

#include <iostream>
#include <vector>

using namespace std;
void backtracking(int n, int m, int str_idx, vector<int>& arr);
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);

  int n, m; cin >> n >> m;
  vector<int> arr;
  backtracking(n, m, 1, arr);
  
  return 0;
}
void backtracking(int n, int m, int str_idx, vector<int>& arr){
  if(arr.size() == m){
    for(int i = 0; i < m; i++){
      cout << arr[i] << ' ';
    }
    cout << '\n';
    return;
  }
  else{
    if(arr.size() + n - str_idx+1 < m){
      return;
    }
  }

  arr.push_back(str_idx);
  backtracking(n, m, str_idx+1, arr); //str_idx포함경우
  arr.pop_back();
  backtracking(n, m, str_idx+1, arr); //str_idx미포함경우
}

배운 점

백트레킹을 해보았다.