브루트포스(2) 재귀

재귀를 쓰면

재귀를 쓰면 모든 경우의 수를 확인하도록 만들 수 있다.

재귀를 써서 모든 경우를 확인하는 경우는 두가지이다.

 

1. 순서가 있는 경우(P)

n개의 수를 나열하는 방법의 수이다.(중복가능)

-> O(n!)

/**
* index -> 현재 수를 놓는 위치
* arr -> 확인하려고 만드는 배열
*/
public void recursive1(int index, int[] arr){
	if(index == arr.length){
		//종료 조건
    }
	for(int i = 1; i <= n; i++){
    	arr[index] = i;
        recursive1(index+1,arr)
	}
}

 

2. 위치(C)

1~n 중 몇개를 사용할 지 판단한다.

-> O(2^n)

/**
* index -> 현재 수를 놓는 위치
* arr -> 확인하려고 만드는 배열
*/
public void recursive2(int cnt, int[] arr, int value, int n){
	if(index == arr.length){
		//종료 조건
    }
    
    if(value > n) return; //종료조건
   
    arr[cnt] = value
    recursive2(cnt+1,arr,value+1,n) // 해당 값을 사용한 경우
    
    recursive2(cnt,arr,value+1,n) // 해당 값을 사용하지 않은 경우
}

 

백 트래킹

불필요한 재귀를 돌지 않도록 조건이 맞지 않으면 사전에 종료시켜버리는 방법이다.