조합 문제를 해결하기 위해 역 추적 알고리즘을 사용하는 코드를 조정하는 방법

Question

문제 설명 :

배열의 모든 조합을 반환합니다. 예를 들어 배열 [1, 2, 3]이면 결과는 다음과 같습니다.

[] 
[1] [2] [3] 
[1, 2] [1, 3] [2, 3] 
[1, 2, 3] 

예이 문제를 해결하는 방법이 많이 있습니다. 하지만 나는 그것을 backtracking 알고리즘으로 해결하려고 노력하고있다. 아래에있는 내 코드입니다 :

def p(arr): 
    ret = [] 
    #using visited boolean array to avoid duplicate traverse and backtracking. 
    visited = [False] * len(arr) 
    def dfs(start_idx, temp) 
     ret.append(temp) 
     for i in range(start_idx, len(arr)): 
      if not visited[i]: 
       visited[i] = True 
       dfs(start_idx + 1, temp + [arr[i]]) 
       visited[i] = False 
    dfs(0, []) 
    return ret 

그것은 [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3], [3, 2]]를 반환, 내 이해에서 오답 [3, 2]

을 가지고, DFS + 되돌아은 왼쪽에서 오른쪽으로되어 한 방향으로 배열을 통과해야한다. 그러나 분명히 [3, 2]는 반대 방향이다.

어떻게 이것을 이해하고 이것을 내 코드로 해결할 수 있습니까?

Answer 1

알고리즘은 어떤 요소가 선택되었는지 추적하기 위해 불리언 목록을 사용합니다. 하지만 좋은 방법은 아닙니다. 일단 요소 을 선택했으면 색인 j> i 인 요소 만 선택할 수있게해야합니다.

start_idx으로 처리하는 것으로 보이지만 사실 재귀 호출에서는 start_idx 만 증가시킵니다.

그래서 빠른 수정 start_indexi+1에 설정하는 것입니다 : 이것은 지금 visited되지 않는 산출

def p(arr): 
    ret = [] 
    #using visited boolean array to avoid duplicate traverse and backtracking. 
    visited = [False] * len(arr) 
    def dfs(start_idx, temp): 
     ret.append(temp) 
     for i in range(start_idx, len(arr)): 
      if not visited[i]: 
       visited[i] = True 
       dfs(i + 1, temp + [arr[i]]) # i instead of start_idx 
       visited[i] = False 
    dfs(0, []) 
    return ret

, 그래서 우리는 이러한 검사를 제거 할 수 있습니다

말했다되고 그건

def p(arr): 
    ret = [] 
    def dfs(start_idx, temp): 
     ret.append(temp) 
     for i in range(start_idx, len(arr)): 
      dfs(i + 1, temp + [arr[i]]) 
    dfs(0, []) 
    return ret

, 내가 사용 제안 itertools.combinations.