백트래킹 정리

 

 

 

 

1 ~ N 중 M개를 뽑아야 한다.

 

 

 

1. 중복 없이 뽑아보자.

 

		for(int i=1; i<N+1; i++){
			if(!used[i]){
				arr[k] = i;
				used[i] = true;
				solve(k+1);
				used[i] = false;
			}
		}

 

 

백트래킹의 기본적인 형태이다.  ( N과 M - 1 )

 

 

2. 중복 없이 + 오름차순으로 뽑아야 한다.

 

 

    public static void bt(int start, int depth) {
        if (depth == M) {
            // print
        }
        for (int i = start; i <= N; i++) {
            arr[depth] = i;
            bt(i + 1, depth + 1);
        }
    }

 

파라미터로 하나 시작점을 정해주고 백트래킹을 돌리면 된다. ( N과 M - 2 )

중복 체크를 안해도 괜찮다. 어차피 시작점이 정해져있다.

 

 

 

3. 중복해서 골라도 된다.

 

 

    public static void bt(int depth) {
        if (depth == M) {
            // print
        }

        for (int i = 1; i <= N; i++) {
            arr[depth] = i;
            bt(depth + 1);
        }
    }

 

중복 확인을 안 하면 된다. dfs 느낌으로. ( N과 M - 3 )

 

 

4. 중복 허용 + 비내림차순

 

 

    public static void bt(int at, int depth) {
        if (depth == M) {
            // print
        }
        for (int i = at; i <= N; i++) {
            arr[depth] = i;
            bt(i, depth + 1);
        }
    }

 

오름차순과 비슷한 형태로 중복 체크를 안 하면 된다. ( N과 M - 4 )

 

 

 

정리해보자.

중복 없이 뽑으려면 visit 배열을 사용하면 되고, 뽑는 수열에 대해 순서가 부여되면 요구사항에 맞춰서 처리해주면 된다. (오름차순으로 출력해야 되면 파라미터로 시작 위치를 정해주는 방식으로 처리한다.)

 

 

 

이 4가지 유형만 제대로 알고 있으면 백트래킹 개념을 몰라서 못 푸는 문제가 생기지는 않는다.

 

 

그리고..

 

        for(int i=1; i<4; i++){                        
            arr[idx] = i;
            bt(sum + i, idx + 1);            
        }
        
        for(int i=1; i<4; i++){  
            sum += i;
            arr[idx] = i;
            bt(sum, idx + 1);            
            sum -= i;
        }

 

 

당연하지만.. 두 코드는 같은 코드이다..