★Backtracking Intermediate I - 10 Solved★

★ 15649 N과 M (1) ★

 

N,M=map(int,input().split())
ans=[]
def track():
    if len(ans) == M: #completed
        print(*ans)
    else:
        for x in range(1,N+1):
            if len(ans) == 0 or x not in ans:
                ans.append(x)
                track()
                ans.pop() #backtrack
track()

 

🙃 backtracking 포스팅 참조

---

★ 15650 N과 M (2) ★

 

N,M=map(int,input().split())
ans=[]
def track():
    if len(ans) == M: #completed
        print(*ans)
    else:
        for x in range(1,N+1):
            if len(ans) == 0 or (x not in ans and ans[-1] < x):
                ans.append(x)
                track()
                ans.pop()
track()

 

🙃 위 N과 M (1)에서 오름차순 조건만 추가

---

★ 15651 N과 M (3) ★

 

N,M=map(int,input().split())
ans=[]
def track():
    if len(ans) == M: #completed
        print(*ans)
    else:
        for i in range(1,N+1):
            ans.append(i)
            track()
            ans.pop()

track()

 

🙃 위 (1)과 (2)와 다르게 도중에 backtracking 되는 조건 없이 바로 track() 쭉 쭉 아래로~

---

★ 15652 N과 M (4) ★

 

N,M=map(int,input().split())
ans=[]
def track():
    if len(ans) == M:
        print(*ans)
    else:
        for i in range(1,N+1):
            if len(ans) < 1 or (len(ans)>=1 and ans[-1]<=i):
                ans.append(i)
                track()
                ans.pop()
track()

 

🙃 중복 허용하고 비내림차순

---

★ 15654 N과 M (5) ★

 

N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
visited=[False]*N
ans=[]
def track():
    if len(ans)==M:
        print(*ans)
    else:
        for x in range(N):
            if not visited[x]:
                visited[x]=True
                ans.append(nums[x])
                track()
                ans.pop()
                visited[x]=False
track()

 

🙃 사전 순 증가 순서로 수열을 출력해야 하므로 sort() 뒤 num not in ans 조건만 넣어 진행

---

★ 15655 N과 M (6) ★

 

N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
ans=[]
def track():
    if len(ans) == M:
        print(*ans)
    else:
        for num in nums:
            if len(ans)<1 or (len(ans)>=1 and ans[-1]<num):
                ans.append(num)
                track()
                ans.pop()
track()

 

🙃 위 (5)에서 증가 조건만 추가. ans에 아무 것도 존재하지 않거나 / 길이가 1이상일 경우는 마지막 원소보다 큰 경우만 해당

---

★ 15656 N과 M (7) ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
ans=[]
def track():
    if len(ans)==M:
        print(*ans)
    else:
        for num in nums:
            ans.append(num)
            track()
            ans.pop()
track()

---

★ 15657 N과 M (8) ★

 

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
nums=list(map(int,input().split()))
nums.sort()
ans=[]
def track():
    if len(ans)==M:
        print(*ans)
    else:
        for num in nums:
            if len(ans)<1 or (len(ans)>=1 and ans[-1]<=num):
                ans.append(num)
                track()
                ans.pop()
track()

---

★ 10974 모든 순열 ★

 

N=int(input())
nums=[x for x in range(1,N+1)]
ans=[]
def track():
    if len(ans) == N:
        print(*ans)
    else:
        for i in range(N):
            if nums[i] not in ans:
                ans.append(nums[i])
                track()
                ans.pop()
track()

 

🎞️ 중복해서 수열이 구성되어 있지는 않으므로 not in ans 조건

---

★ 5568 카드 놓기 ★

 

import sys
input=sys.stdin.readline

n=int(input())
k=int(input())
numbers,visited=[],[False]*n
ans=set()
cards=[input().rstrip() for _ in range(n)] #different numbers marked in each cards

def track(depth):
    if depth==k: #list of strings
        number=''.join(numbers)
        ans.add(number)
        return
    else:
        for i_card in range(len(cards)):
            if not visited[i_card]:
                visited[i_card] = True
                numbers.append(cards[i_card])
                track(depth+1)
                visited[i_card] = False
                numbers.pop()

track(0)
print(len(ans))

 

🎞️ 카드 1번씩만 고르므로 visited [] 활용 / 서로 다른 카드를 골라도 같은 수일 가능성이 있으므로 set() 활용 / depth 인자로 카드 개수 판별

---