39.組合せ合計(Python)

もっと素晴らしい内容は、「力ボタン中等問題」に注目してください.
タイトル
難易度:★☆☆タイプ:配列方法:遡及法
重複要素のない配列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:遡及法
私たちは遡及法を用いてこの問題を解決した.遡及法の思想は、適切でなければ、前のステップに戻ることだ.
遡及操作を実現するための関数helperを書きます.
入力パラメータ

現在考察する要素の所在する下標(index);

は、現在までの和(cur_sum)に加算される.

現在およびcur_listを構成する一時リスト(cur_list)sumが使用したすべての加算数.

操作フロー

操作が合法かどうかを判断し、操作回数を制限するために使用され、2つの判断条件がある:(1)現在考察されている要素の所在する下標iが合法かどうか、境界が現れるかどうか;(2)現在までの和cur_sumが目標値targetを超えたかどうか、超えた場合は操作する必要はありません.

条件が満たされたか否か、すなわちcur_sumが目標値targetに等しいかどうか、等しい場合はcur_を構成するsumの各加算cur_リストは結果リストresに追加されます.

現在およびcur_について考察するsumに現在の要素candidates[index,cur_sum+candidates[index],cur_list+[candidates[index])が入っている場合.

現在およびcur_について考察するsumに現在の要素が入っていない場合、すなわち現在の要素をスキップし、次の要素:helper(index+1,cur_sum,cur_list)を考察する.

遡及法の真髄はステップ3とステップ4にあり,可能なすべての組合せを遍歴することができる.遡及法の説明とその他のテーマについては、「遡及法総説」に移動してください.
注意:配列内の要素が重複していないため、ソートは使用できません.

class Solution:
    def combinationSum(self, candidates, target):
        """
        :param candidates: List[int]
        :param target: int
        :return:
        """

        def helper(index, cur_sum, cur_list):
            """
            :param i:        
            :param cur_sum:    
            :param cur_list:   cur_sum     
            :return:
            """

            #        
            if cur_sum > target or index == len(candidates):
                return

            #             ，       
            if cur_sum == target:
                res.append(cur_list)
                return

            #       candidates[i]
            helper(index,  cur_sum + candidates[i], cur_list + [candidates[i]])

            #        
            helper(index+1, cur_sum, cur_list)

        candidates.sort()
        res = []
        helper(0, 0, [])
        return res

質問やアドバイスがあれば、コメントエリアへようこそ~