브루트 포스 - 백준 15650 [Python]

재귀함수로 풀 수 있는 브루트 포스

1. 순서 : N가지가 있을 때 M를 순서대로 뽑을 경우 O(N!)
2. 선택 : N가지에 대해서 선택/선택하지 않는 것 O(2^N)

Problem)

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

15649번: N과 M (1)

 

Solution)

재귀 : 어떤 위치에 올 수 있는 수를 결정해 주는 것

선택 : 그 위치에 있는 것을 선택할지 말지 결정하는 것

 

Answer)

import sys
n,m = map(int,input().split())
c = [False]*(n+1)
a = [0]*m

def go(index, start, n, m):
    if index == m:
        sys.stdout.write(' '.join(map(str,a))+'\n')
        return
    for i in range(start, n+1):
        if c[i]:
            continue
        c[i] = True
        a[index] = i
        go(index+1, i+1, n, m)
        c[i] = False

go(0,1,n,m)