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

Pythonで合計kになる個別の組み合わせの数を見つけるプログラム

numsと呼ばれる別個の数と別の数kのリストがあるとすると、合計でkになる別個の組み合わせの数を見つける必要があります。組み合わせを作成するときに数字を再利用できます。

したがって、入力がnums =[2、4、5] k =4のような場合、[2、2]と[4]のような2つのグループを作成できるため、出力は2になります。

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

  • table：=サイズk + 1のリスト、0で埋める
  • table [0]：=1
  • numsの各numに対して、実行します
    • numからkの範囲のiについては、
      • table [i]：=table [i] + table [i --num]
  • リターンテーブル[k]

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

サンプルコード

class Solution:
   def solve(self, nums, k):
      table = [1] + [0] * k

      for num in nums:
         for i in range(num, k + 1):
            table[i] += table[i - num]

         return table[k]

ob = Solution()
nums = [2, 4, 5]
k = 4
print(ob.solve(nums, k))

入力

[2, 4, 5], 4

出力

2

  1. 数の偶数因子の合計を見つけるためのPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します- 問題の説明 数値入力nが与えられた場合、タスクは数値の偶数因子の合計を見つけることです。 ここでは、最初にすべての奇妙な要因を排除する必要があります。 入力された数値が奇数の場合、偶数の因数はなく、直接ゼロを返します。それ以外の場合は、以下のコードのアプローチに従います。 以下は実装です- 例 import math # Returns sum of all even factors of n. def sumofFactors(n) :    # If n is odd   &nbs

  2. 数の因子の最小合計を見つけるためのPythonプログラム

    この記事では、以下に示す問題ステートメントの解決策について学習します- 問題の説明 入力された数値を指定して、指定された数値の因子の最小合計を求めます。 ここでは、すべての因子とそれに対応する合計を計算し、それらの中から最小値を見つけます。 したがって、数の積の最小合計を見つけるために、積の素因数の合計を見つけます。 これが問題の反復実装です- 例 #iterative approach def findMinSum(num):    sum_ = 0    # Find factors of number and add to the sum