[BOJ]15650 NとM(2)(逆トレース)


1.質問


https://www.acmicpc.net/problem/15650

2.解法


1) ⭕RIGHT⭕

  • コード
  • #include <iostream>
    #include <vector>
    using namespace std;
    
    int N, M;
    vector<int> v;
    bool visited[8];
    
    void backtracking(int level)
    {
    	if (level == M)
    	{
    		for (int i = 0; i < v.size(); ++i)
    			cout << v[i] << ' ';
    		cout << '\n';
    		return;
    	}
    	for (int i = 1; i <= N; ++i)
    	{
    		if (!visited[i]) {
    			if(v.empty()||i>v.back())
    			{
    				visited[i] = true;
    				v.push_back(i);
    				backtracking(level + 1);
    				v.pop_back();
    				visited[i] = false;
    			}
    		}
    	}
    }
    
    int main() {
    	ios::sync_with_stdio(false);
    	cin.tie(NULL); cout.tie(NULL);
    
    	cin >> N >> M;
    
    	backtracking(0);
    	
    	return 0;
    }
  • その他の説明
    -NおよびM(1)とは異なる部分
    if (v.empty() || i > v.back())
    平均数列は昇順に並べなければなりません.
    ブラウズは、最初に選択した数の列または現在ブラウズする数の列が前の数の列より大きい場合にのみ行います.