さかのぼる

leetcode——再帰、遡及
遡及再帰は暴利貧挙の変体であり,多くの複雑な問題は,再帰遡及法によって最終解を見つけることができ,欠点は時間複雑度が高いことである.アルゴリズムが実際に動作する時間を減らすために、剪断操作によってアルゴリズムが再帰を継続するかどうかを制限することができ、合理的な剪断は指数級の複雑度のアルゴリズムを可能にし、比較的短い時間で検索を完了することができる.そのため,再帰遡及法では,剪定をどのように設計するかが重要である.
次にleetcodeブラシの過程で出会ったいくつかの再帰遡及に関する問題をまとめて、後でめくって、間違いと不足点があれば、相応のアドバイスを期待します.
1、リスト要素の全配置

             ，           。

  :

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

問題解決の考え方:
タイトルの与えられた入力では,すべての可能な全配列を出力し,各位置iにおいてそれぞれn中の可能性があり,nは重複入力のない個数を表し,最も簡単である,貧挙により,[1,1,1,[1,2]...,[3,3,3]の27種類の可能な結果が得られるが,その中には要求に合致しない複数の配列が含まれている.重複する要素を持つことは要求に合わない.これらの結果をフィルタリングする必要があります
ここで採用する方法は再帰的遡及である

class Solution:
    def permute(self, nums):
        answer =[]
        result =[]
        length =len(nums)
        idx=0
        self.DFS(nums,answer,result,s,idx,length)
        return result

    def DFS(self,nums,answer,result,s,idx,length):

        if idx==length :
            s.append(answer[:])
            if len(list(set(answer)))==length:
                result.append(answer[:])
            return

        elif idx0:
            if answer[-1] in answer[:-1]:
                return

        for i in range(length):
            #    ， pop  
            answer.append(nums[i])
            self.DFS(nums,answer,result,s,idx+1,length)

            answer.pop()

if __name__ == '__main__':
    example =Solution()
    nums =[1,2,3]
    res=example.permute(nums)
    print('final :{}'.format(res))

ここでは、深度優先探索の手法を用いて、すべての可能な要素を巡回し、現在の結果が指定数nに達していないと仮定すると、現在の要素を格納し、自身を再帰的に呼び出す.ここでは2つの選択があり、第1に、組合せ結果がnに達したと仮定し、ツリーの奥に到着したことを示し、[1,1,2],[2,1,3]のような結果を得ることができる.しかし、このような結果はすべて有効ではなく、重複要素を持つリストは無効であり、ここではsetを使用して重さを除去し、重さを除去した要素の個数は依然としてn個であり、この結果が有効であることを示し、最終的な戻り値に格納される.
上記のやり方は、再帰的に用いられているが、実質的には貧乏であり、実際の状況では、[1,1,...],[2,2,...]という例を貧乏に挙げると、後の要素が何であるかにかかわらず、現在のこのsampleが要求に合致していることが明らかになった.この場合、停止し、前のノードに遡ることができ、再帰の回数を減らすことができる.これが枝切りです.したがって、インデックス番号がnより小さい場合、現在のsampleの結果answerの最後の要素が前の要素と重複しているかどうかを判別し、重複があると仮定し、直接returnを返し、pop操作を使用して前のノードに遡る.
ここで問題があります.resultの後ろにappend answerがあるたびにanswer[:]を使用しなければなりません.answerを使用することはできません(空を返します.後ろのpop操作で要素がポップアップされた可能性があります).理解していません.
かっこ生成

   n          ，        ，                    。

  ，   n = 3，     ：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

3.組合せ合計
重複要素のない配列candidatesとターゲット数targetを指定し、candidatesのすべての数値とtargetの組合せを見つけます.
candidatesの数字は、無制限に繰り返し選択できます.
説明:
すべての数字(targetを含む)は正の整数です.解セットに重複する組合せを含めることはできません.例1:
入力:candidates=[2,3,6,7],target=7,解セット:[[7],[2,2,3]]例2:
入力:candidates=[2,3,5],target=8,解セット:[[2,2,2,2],[2,3,3],[3,5]]
考え方:
深度優先検索にクリップを加えて問題を解決するには、まず、ソートされていないリストをソートする必要があります.後ろの枝切り操作が便利です.リストから1つの要素を選択するたびに、要素を繰り返し選択できるため、再帰的な次の要素は前の要素から始まり、後ろに順次遍歴し、遡及します.

class Solution(object):
    '''
                            ，                 ，
                ， “  ”  （       ）
               。           。
           ，    ，              。
    ----------------------------------------------
                               
    ------------------------------------------------
                        ，                    ，         。
    ***          ，          ，        。
    '''
    def __init__(self):
        self.a =0
    def combinationSum(self, candidates, target):
        answer =[]
        result =[]
        candidates.sort()
        length =len(candidates)
        self.DFS(candidates,target,0,length,answer,result)
        print('a :{}'.format(self.a))
        return result


    def DFS(self,candidates,target,start,length ,answer,result):
        self.a+=1
        for i in range(start,length):
            if target>0:
                #target   0     
                answer.append(candidates[i])
                self.DFS(candidates,target-candidates[i],i,length,answer,result)
                answer.pop()
                if target-candidates[i]<=0:
                    break
            elif target<0:
                #target    0       ，   
                return
            else:
                #target =0     ，            ，    ，
                #     ,      

                result.append(answer[:])  #   answer，  pop  
                return

合計のバリエーションを組み合わせて要素を繰り返し選択することはできません.candidatesには繰り返しの要素があります.この場合、上記のプログラムを少し修正するだけで、再帰的に呼び出されたidxが次の数値であるidx=i+1になり、最後のビットが要求に合致して最後の結果に正しくロードできない場合を解決するために、追加の判断が必要になります.

class Solution:
    def combinationSum2(self, candidates, target):
        """
        candidates        ，           
          DFS  

        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        answer=[]
        result =[]
        candidates.sort()
        idx =0
        length =len(candidates)
        self.DFS(target,candidates,answer,result,idx,length)
        return result

    def DFS(self,target,candidates,answer,result,idx,length):

		#           
        if idx==length and target==0:
			#  
            if answer[:] not in result:
                result.append(answer[:])
            return

        for i in range(idx,length):
            if target==0 :
				#  
                if answer[:] not in result:
                    result.append(answer[:])
                return

            elif target<0:
                return

            else:
                answer.append(candidates[i])
                self.DFS(target-candidates[i],candidates,answer,result,i+1,length)

                answer.pop()
                if target-candidates[i]<=0:
                    break