N과 M 시리즈-백트래킹

N과 M (1)

def dfs():
    if len(result)==m: # m개를 골랐으면 출력
        print(*result)
        return
    for i in range(1,n+1):
        if visited[i]==0: # 방문을 안했으면
            result.append(i) # 값을 저장
            visited[i]=1 # 방문 체크
            dfs()
            result.pop() # 값 제거
            visited[i]=0 # 방문 원래대로 돌리기

n,m=map(int,input().split())
result=[]
visited=[0]*(n+1)
dfs()

 

N과 M (2)

def dfs(s):
    if len(result)==m: # m개를 골랐으면 출력
        print(*result)
        return
    for i in range(s,n+1):
        if visited[i]==0: # 방문을 안했으면
            result.append(i) # 값을 저장
            visited[i]=1 # 방문 체크
            dfs(i+1) # 다음 값부터 
            result.pop() # 값 제거
            visited[i]=0 # 방문 원래대로 돌리기

n,m=map(int,input().split())
result=[]
visited=[0]*(n+1)
dfs(1)

 

N과 M (3)

def dfs():
    if len(result)==m: # m개를 골랐으면 출력
        print(*result)
        return
    for i in range(1,n+1):
        result.append(i) # 값을 저장
        dfs()
        result.pop() # 값 제거
           

n,m=map(int,input().split())
result=[]
dfs()
# 중복계산이 필요없으므로 visited를 삭제

 

N과 M (4)

def dfs(s):
    if len(result)==m: # m개를 골랐으면 출력
        print(*result)
        return
    for i in range(s,n+1):
        result.append(i) # 값을 저장
        dfs(i)
        result.pop() # 값 제거
           

n,m=map(int,input().split())
result=[]
dfs(1)

 

N과 M (5)

def dfs():
    if len(result)==m:
        print(*result)
        return
    for i in range(n):
        if not visited[i]:
            result.append(n_list[i])
            visited[i]=1
            dfs()
            result.pop()
            visited[i]=0


n, m = map(int,input().split())
n_list=list(map(int,input().split()))
result=[]
n_list.sort()
visited=[0]*n
dfs()

 

N과 M (6)

def dfs(cnt,idx):
    if cnt==m: # m개를 뽑았으면
        print(*result) # 결과를 출력
        return
    for i in range(idx,n):
        result.append(n_list[i])
        dfs(cnt+1, i+1)
        result.pop()

n,m=map(int,input().split())
n_list=list(map(int, input().split()))
n_list.sort()
result=[]
dfs(0,0)

 

N과 M (7)

def dfs():
    if len(result)==m:
        print(*result)
        return
    for i in range(n):
        result.append(n_list[i])
        dfs()
        result.pop()
        
n, m = map(int,input().split())
n_list=list(map(int,input().split()))
result=[]
n_list.sort()
dfs()

 

N과 M (8)

def dfs(s):
    if len(result)==m:
        print(*result)
        return
    for i in range(s,n):
        result.append(n_list[i])
        dfs(i)
        result.pop()


n, m = map(int,input().split())
n_list=list(map(int,input().split()))
result=[]
n_list.sort()
dfs(0)

 

N과 M (9)

def dfs():
    if len(result)==m:
        print(*result)
        return
    temp=0 # 중복을 확인하기 위한 변수
    for i in range(n):
        if visited[i]==0 and temp!=n_list[i]: # 방문하지 않았고, 중복이 아니라면
            result.append(n_list[i]) # 결과에 추가
            temp=n_list[i] # 다음에 중복을 확인하기 위한 값으로 설정
            visited[i]=1
            dfs()
            result.pop()
            visited[i]=0

n, m = map(int,input().split())
n_list=list(map(int,input().split()))
result=[]
visited=[0]*n
n_list.sort()
dfs()

 

N과 M (10)

# 비내림차순
# 중복 수열 제거
def dfs(s):
    if len(result)==m:
        print(*result)
        return
    temp=0 # 중복을 확인하기 위한 변수
    for i in range(s,n):
        if visited[i]==0 and temp!=n_list[i]: # 방문하지 않았고, 중복이 아니라면
            result.append(n_list[i]) # 결과에 추가
            temp=n_list[i] # 다음에 중복을 확인하기 위한 값으로 설정
            visited[i]=1
            dfs(i)
            result.pop()
            visited[i]=0

n, m = map(int,input().split())
n_list=list(map(int,input().split()))
result=[]
visited=[0]*n
n_list.sort()
dfs(0)

 

N과 M (11)

def dfs():
    if len(result)==m:
        print(*result)
        return
    temp=0 # 중복을 확인하기 위한 변수
    for i in range(n):
        if temp!=n_list[i]: # 방문하지 않았고, 중복이 아니라면
            result.append(n_list[i]) # 결과에 추가
            temp=n_list[i] # 다음에 중복을 확인하기 위한 값으로 설정
            dfs()
            result.pop()

n, m = map(int,input().split())
n_list=list(map(int,input().split()))
result=[]
n_list.sort()
dfs()

 

N과 M (12)

def dfs(s):
    if len(result)==m:
        print(*result)
        return
    temp=0 # 중복을 확인하기 위한 변수
    for i in range(s,n):
        if temp!=n_list[i]: # 방문하지 않았고, 중복이 아니라면
            result.append(n_list[i]) # 결과에 추가
            temp=n_list[i] # 다음에 중복을 확인하기 위한 값으로 설정
            dfs(i)
            result.pop()
          
n, m = map(int,input().split())
n_list=list(map(int,input().split()))
result=[]
n_list.sort()
dfs(0)