数字の固定されたセットから合計を得るすべての可能な方法を見つける

Question

質問はかなり簡単です。集合{2,4,6}があります。予想される答えは、数字6を得るためのすべての可能な順列です。 -

{2,2,2}、{2,4}、{4,2}、{6}

私が試したこと： -

私はこの一般的な "硬貨の変更"の質問を使用してこの問題にアプローチしようとしています。しかし、コインの変更の順​​列はそこにありません。 {2,4}と{4,2}は同じものとみなされます。ここに私のコードです。順列については説明しません。

public static int NumberOfWays(int sum) 
{ 
    int [][] memMatrix = new int [7][sum+1]; 
    for (int i = 2 ; i <= 6 ; i += 2) 
    { 
     for (int j = 0 ; j <= sum ; j += 2) 
     { 
      if (i == 2) 
      { 
       //using only 2 , there is only 1 way to get the sum 
       memMatrix[i][j] = 1; 
      } 
      else if (i > j) 
      { 
       //if total sum is less than the newly used denomination , then the number of ways will always remain same 
       memMatrix[i][j] = memMatrix[i - 2][j]; 
      } 
      else 
      { 
       //if this is the case then need to calculate without using the denomination + using the denomination 
       memMatrix[i][j] = memMatrix[i - 2][j] + memMatrix[i][j - i]; 
      } 
     } 
    } 
    for (int i = 2 ; i <= 6 ; i += 2) 
    { 
     for (int j = 2 ; j <= sum ; j += 2) 
     { 
      System.out.print(memMatrix[i][j]+" "); 
     } 
     System.out.print("\n"); 
    } 

    return memMatrix[6][sum]; 
} 

ここでは、マトリックスと一緒になる出力を示します。順列についてもどうやって説明できますか？

1 1 1 
1 2 2 
1 2 3 
The number of ways to get 6 = 3 

Answer 1

私は解決策を得ました。それはかなり簡単です。コードはコメントされています。トレースを少し必要とするかもしれません。

#include <bits/stdc++.h> 
using namespace std; 

    // Function to find the total number of ways to get change of N from 
// unlimited supply of coins in set S 
int count(int S[], int n, int N) 
{ 
// if total is 0, return 1 
if (N == 0) 
    return 1; 

// return 0 if total become negative 
if (N < 0) 
    return 0; 

// initialize total number of ways to 0 
int res = 0; 

// do for each coin 
for (int i = 0; i < n; i++) 
{ 
    // recuse to see if total can be reached by including 
    // current coin S[i] 
    res += count(S, n, N - S[i]); 
} 

// return total number of ways 
return res; 
} 

// main function 
int main() 
{ 
// n coins of given denominations 
int S[] = { 1, 2, 3 }; 
int n = sizeof(S)/sizeof(S[0]); 

// Total Change required 
int N = 4; 

cout << "Total number of ways to get desired change is " 
     << count(S, n, N); 

return 0; 
}