[백준 15651] N과 M(3)

요구사항

중복을 허용한 순열 구하기

 

풀이

중복을 허용함으로 visit 배열이 없이 백트래킹으로 탐색한다

 

#include <stdio.h>
#include <algorithm>
#include <list>
//#include "Windows.h"
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>

using namespace std;
 
const int PN=23;
const int HASHSIZE=12371;

int table[HASHSIZE][50];
char hash_table[HASHSIZE][100];
int hash_size=0;

unsigned int get_key(char str[]){
	unsigned int key=0, p=1;
	for(int i=0 ; str[i]!=0; i++){
		key +=(str[i]*p);
		p*=PN;
	}
	return key%HASHSIZE;
}

void add(char str[]){
	unsigned int key=get_key(str);
	int len=0;
	for(len=0; str[len]!=0; len++){
		hash_table[hash_size][len]=str[len];
	}
	hash_table[hash_size][len]=0;

	int &size=table[key][0];
	table[key][++size]=hash_size++;
}

int str_cmp(char a[], char b[]){
	int i=0,j=0;
	while(a[i]){
		if(a[i++]!=b[j++]){
			i--,j--;
			break;
		}
	}
	return a[i]-b[j];
}
int contain(char str[]){
	unsigned int key=get_key(str);
	int size=table[key][0];
	for(int i=1; i <=size; i++){
		int pos=table[key][i];
		if(str_cmp(hash_table[pos],str) ==0){
			return pos;
		}
	}
	return -1;
}
bool remove(char str[]){
	unsigned int key=get_key(str);
	int &size=table[key][0];
	for(int i=1; i <=size ; i++){
		int pos=table[key][i];
		if(str_cmp(hash_table[pos],str)==0){
			for(int j=i; j<size ; j++){
				table[key][j]=table[key][j+1];
			}
			size--;
			return true;
		}
	}
	return false;
}

int make_int(int min,int max){
	return rand()%(max-min)+min;
}
char make_char(){
	int val=rand()%52;
	if(val<26){
		return static_cast<char>('a'+val);
	}
	return static_cast<char>('A'+val-26);
}
map<char*,int> test;
char input[12371][120];
int n,m;
vector<int> v;
int a[100];
int visit[100];
void dfs(int now,int cnt){
	if(cnt==m){
		for(int i=0 ; i <v.size();i++){
			printf("%d ",v[i]);
		}
		printf("\n");
		return;
	}
	for(int i = 0; i < n ; i++){
		//if(visit[i]==1) continue;
		//visit[i]=1;
		v.push_back(a[i]);
		dfs(i+1,cnt+1);
		//visit[i]=0;
		v.pop_back();
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0 ; i <n ; i++){
		a[i]=i+1;
	}
	dfs(0,0);
}