Combination implementation w. Backtracking

m개중 n개 뽑기

• example code

def choose_n(cnt, last_idx):
	if cnt == n:
    	DO SOMETHING YOU WANT with m things
       	return
   	
    for i in range(last_idx + 1, len(hospitals)):
    	visited[i] = True
        choose_n(cnt + 1, i)
        visited[i] = False

choose_n(0, -1)

hand debugging

let n is 3 and m is 5 ... 5C3

choose_n(0, -1) -> visited[0] = True, call choose_n(1, 0)
choose_n(1, 0) -> visited[1] = True, call choose_n(2, 1)
choose_n(2, 1) -> visited[2] = True, call choose_n(3, 2)

choose_n(3, 2) -> return	[0, 1, 2]
choose_n(2, 1) -> visited[2] = False, visited[3] = True, call choose_n(3, 3)
choose_n(3, 3) -> return	[0, 1, 3]

choose_n(2, 1) -> visited[3] = False, visited[4] = True, call choose_n(3, 4)
choose_n(3, 4) -> return	[0, 1, 4]

choose_n(2, 1) -> visited[4] = False, return

choose_n(1, 0) -> visited[1] = False, visited[2] = True, call choose_n(2, 2)
choose_n(2, 2) -> visited[3] = True, call choose_n(3, 3)
choose_n(3, 3) -> return	[0, 2, 3]

choose_n(2, 2) -> visited[3] = False, visited[4] = True, call choose_n(3, 4)
choose_n(3, 4) -> return	[0, 2, 4]

choose_n(2, 2) -> visited[4] = False, return

choose_n(1, 0) -> visited[2] = False, visited[3] = True, call choose_n(2, 3)
choose_n(2, 3) -> visited[4] = True, call choose_n(3, 4)
choose_n(3, 4) -> return	[0, 3, 4]

choose_n(2, 3) -> visited[4] = False, return

choose_n(1, 0) -> visited[3] = False, visited[4] = True, call choose_n(2, 4)
choose_n(2, 4) -> return

choose_n(1, 0) -> visited[4] = False, return

choose_n(0, -1) -> visited[0] = False, visited[1] = True, call choose_n(1, 1)
choose_n(1, 1) -> visited[2] = True, call choose_n(2, 2)
choose_n(2, 2) -> visited[3] = True, call choose_n(3, 3)
choose_n(3, 3) -> return	[1, 2, 3]

choose_n(2, 2) -> visited[3] = False, visited[4] = True, call choose_n(3, 4)
choose_n(3, 4) -> return	[1, 2, 4]

choose_n(2, 2) -> visited[4] = False, return
choose_n(1, 1) -> visited[2] = False, visited[3] = True, call choose_n(2, 3)
choose_n(2, 3) -> visited[4] = True, call choose_n(3, 4)
choose_n(3, 4) -> return	[1, 3, 4]

choose_n(2, 3) -> visited[4] = False, return
choose_n(1, 1) -> visited[3] = False, visited[4] = True, call choose_n(2, 4)
choose_n(2, 4) -> return
choose_n(1, 1) -> return

choose_n(0, -1) -> visited[1] = False, visited[2] = True, call choose_n(1, 2)

...

• 순서
  0,1,2 -> 0,1,3 -> 0,1,4 -> 0,2,3 -> 0,2,4 -> 0,3,4
  1,2,3 -> 1,2,4 -> 1,3,4
  2,3,4

총 10 ... 5C3 = 10