バックトラッキングアルゴリズムを使用して組み合わせの問題を解決するコードを調整する方法

Question

問題の説明：

すべての配列の組み合わせを返します。たとえば配列[1,2,3]がある場合、結果は次のようになります。

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

はいこれを解決する方法はたくさんあります。私はバックトラッキングアルゴリズムでそれを解決しようとしています。以下の私のコードです：それは私の理解から、間違った答え[3, 2]

を持っている[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3], [3, 2]]を返し

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 

、DFS +バックトラックは右に左にされて一方向に配列を横断しなければなりません。明らかに[3,2]は逆の方向です。

これを理解する方法とこれを私のコードで修正する方法は？

Answer 1

アルゴリズムでは、ブール値のリストを使用して、選択されている要素を追跡します。しかし、これは良い方法ではありません。一度要素を選択した場合は、インデックスj> iの要素のみを選択できるようにしてください。

あなたはstart_idxでこれを行うようですが、実際には再帰呼び出しではstart_idxだけインクリメントします。

だから、クイックフィックスはi+1にstart_indexを設定することです：

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

これは、互換性のために残さvisitedをもたらし、私たちはこれらのチェックを削除することができます。

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。