C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++での組み合わせ合計IV

すべて正の数の整数配列があり、すべての要素が一意であると仮定し、可能な組み合わせの数を見つけて、合計すると正の整数ターゲットを取得します。

したがって、配列が[1、2、3]で、ターゲットが4の場合、可能な組み合わせは[[1,1,1,1]、[1,1,2]、[1,2,1]になります。 、[2,1,1]、[1,3]、[3,1]、[2、2]]なので、出力は7になります。

これを解決するには、次の手順に従います-

  • solve（）と呼ばれる1つの再帰関数があると仮定します。これは、動的プログラミングタスク用に配列、ターゲット、および別の配列を取得します。プロセスは次のようになります
  • target =0の場合、1を返します
  • dp [target]が-1でない場合は、dp [target]
    • を返します。
  • ans：=0
  • 0からnumsの範囲のiの場合
    • ターゲットの場合>=nums [i]
      • ans：=ans + resolve（nums、target – nums [i]、dp）
  • set dp [target]：=ans
  • 回答を返す
例（C ++）

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int combinationSum4(vector<int>& nums, int target) {
      vector <int> dp(target + 1, -1);
      return helper(nums, target, dp);
   }
   int helper(vector <int>& nums, int target, vector <int>& dp){
      if(target == 0)return 1;
      if(dp[target] != -1)return dp[target];
      int ans = 0;
      for(int i = 0; i < nums.size(); i++){
         if(target >= nums[i]){
            ans += helper(nums, target - nums[i], dp);
         }
      }
      return dp[target] = ans;
   }
};
main(){
   Solution ob;
   vector<int> v = {1,2,3};
   cout << ob.combinationSum4(v, 4);
}

入力

[1,2,3]
4

出力

7

  1. C ++でのアリコートの合計？

    ここで、アリコートの合計は何ですか？ nのアリコート和は、nを除くnのすべての完全な因子の合計です。たとえば、数値が20の場合、完全な因数は（1、2、4、5、10）です。したがって、アリコートの合計は22です。 興味深い事実の1つは、ある数のアリコートの合計がその数そのものである場合、その数は完全数であるということです。たとえば、6。係数は（1、2、3）です。アリコートの合計は1+2 + 3=6です。 次のアルゴリズムを使用してアリコートの合計を取得する方法を見てみましょう。 アルゴリズム getAliquotSum（n） begin    sum := 0 &nbs

  2. Pythonでの組み合わせの合計

    候補番号のセット（すべての要素が一意）とターゲット番号があるとします。候補者の数が特定のターゲットに合計される候補者のすべての一意の組み合わせを見つける必要があります。同じ繰り返し数を候補者から無制限に選択することができます。したがって、要素が[2,3,6,7]で、ターゲット値が7の場合、可能な出力は[[7]、[2,2,3]]になります。 手順を見てみましょう- これを再帰的に解決します。再帰関数の名前はsolve（）です。これには、結果を格納するための配列、レコードを保持するための1つのマップ、ターゲット値、および個別の要素のリストが必要です。最初はres配列で、マップは空です。解決