[アルゴリズム]DFSと遡及追跡(+N queen,部分数列の和)

バックトラッキングとは?

DFS

N*N Queen問題

code

N  = int(input())

ans = 0
col = [0] * N

def check(x):
  for i in range(x):
    if col[x]==col[i] or (x-i ==abs(col[x]-col[i])) : # 이전까지 중 하나라도 under attack 이면
      return False
  return True

def backtrack(x):
  global ans
  if x==N:
    ans+=1
    return 
  else:
    for i in range(N): # 0-n-1 까지 각각의 node 별 탐색
      col[x]=i # x는 인풋, i 는 itertating

      if check(x): # checking 시 under attack 상태가 아니라면
        backtrack(x+1) # 다음 자식 노드로 넘어감

backtrack(0)
print(ans)

サブセット問題の集合

import sys

inp = sys.stdin.readline
n, s = map(int,inp().split())
sets = list(map(int, inp().split()))
ans=0
def backtrack(x,subset):# x는 sets에 대응될 index
    global ans
    if x>=n:
        return

    subset +=sets[x] #input으로 받은 부분합에 더함

    if subset==s:
        ans+=1
    # if subset<s: # 값들이 양수로만 이루어져 있을 경우 활용하면 좋을 조건
    backtrack(x+1, subset) # 해당 값을 더한 부분합.

    backtrack(x+1, subset-sets[x]) # 안더한 부분합.

backtrack(0,0)
print(ans)

振り返る😁