Finden Sie alle möglichen Möglichkeiten, eine Summe aus einer festen Reihe von Zahlen zu erhalten

Question

Die Frage ist ziemlich einfach. Es gibt eine Menge {2,4,6}. Die erwartete Antwort alle möglichen Permutationen ist die Nummer 6. So zu bekommen, wird die Antwort sein: -

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

Was ich versucht habe: -

Ich versuche, dieses Problem mit der beliebten "Münzwechsel" -Frage zu nähern. Aber im Münzwechsel sind Permutationen nicht vorhanden. Die Mittel {2,4} und {4,2} werden als gleich angesehen. Hier ist mein Code. Permutationen werden nicht berücksichtigt.

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]; 
} 

Hier ist der Ausgang, den ich mit der Matrix bekomme. Wie kann ich Permutationen auch berücksichtigen?

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

Answer 1

Ich habe die Lösung. Es ist ziemlich einfach. Der Code ist kommentiert. Es könnte ein wenig Nachverfolgung erfordern.

#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; 
}