原文:
给定一个正整数 n ，任务是找出所有的正整数组合加起来的给定整数 n 。程序应该只打印组合，而不是排列，并且组合中的所有整数必须是不同的。例如，对于输入 3，应该打印 1，2 或 2，1，而不能打印 1，1，1，1，因为整数是不同的。 例:
输入: n = 3 输出: 1 2 3 输入: n = 7 输出: 1 2 4 1 6 2 5 3 4 7
方法:该方法是这里。用来得到所有不同元素的想法是，首先我们找到所有相加得到总和的元素 n 。然后我们迭代每个元素并将元素存储到中。将元素存储到集合中会删除所有重复的元素，然后我们将集合的元素之和相加，并检查它是否等于 n 。 以下是上述方法的实施:
c
// c implementation of the approach
#include
using namespace std;
/* arr[] to store all the distinct elements
index - next location in array
num - given number
reducednum - reduced number */
void findcombinationsutil(int arr[], int index,
int n, int red_num)
{
// set to store all the
// distinct elements
set s;
int sum = 0;
// base condition
if (red_num < 0) {
return;
}
if (red_num == 0) {
// iterate over all the elements
// and store it into the set
for (int i = 0; i < index; i ) {
s.insert(arr[i]);
}
// calculate the sum of all
// the elements of the set
for (auto itr = s.begin();
itr != s.end(); itr ) {
sum = sum (*itr);
}
// compare whether the sum is equal to n or not,
// if it is equal to n print the numbers
if (sum == n) {
for (auto i = s.begin();
i != s.end(); i ) {
cout << *i << " ";
}
cout << endl;
return;
}
}
// find previous number stored in the array
int prev = (index == 0) ? 1 : arr[index - 1];
for (int k = prev; k <= n; k ) {
// store all the numbers recursively
// into the arr[]
arr[index] = k;
findcombinationsutil(arr, index 1,
n, red_num - k);
}
}
// function to find all the
// distinct combinations of n
void findcombinations(int n)
{
int a[n];
findcombinationsutil(a, 0, n, n);
}
// driver code
int main()
{
int n = 7;
findcombinations(n);
return 0;
}
java 语言(一种计算机语言，尤用于创建网站)
// java implementation of the approach
import java.util.*;
class gfg
{
/* arr[] to store all the distinct elements
index - next location in array
num - given number
reducednum - reduced number */
static void findcombinationsutil(int arr[], int index,
int n, int red_num)
{
// set to store all the
// distinct elements
hashset s = new hashset<>();
int sum = 0;
// base condition
if (red_num < 0)
{
return;
}
if (red_num == 0)
{
// iterate over all the elements
// and store it into the set
for (int i = 0; i < index; i )
{
s.add(arr[i]);
}
// calculate the sum of all
// the elements of the set
for (integer itr : s)
{
sum = sum itr;
}
// compare whether the sum is equal to n or not,
// if it is equal to n print the numbers
if (sum == n)
{
for (integer i : s)
{
system.out.print(i " ");
}
system.out.println();
return;
}
}
// find previous number stored in the array
int prev = (index == 0) ? 1 : arr[index - 1];
for (int k = prev; k <= n; k )
{
// store all the numbers recursively
// into the arr[]
if(index < n)
{
arr[index] = k;
findcombinationsutil(arr, index 1,
n, red_num - k);
}
}
}
// function to find all the
// distinct combinations of n
static void findcombinations(int n)
{
int []a = new int[n];
findcombinationsutil(a, 0, n, n);
}
// driver code
public static void main(string arr[])
{
int n = 7;
findcombinations(n);
}
}
/* this code contributed by princiraj1992 */
python 3
# python3 implementation of the approach
# arr[] to store all the distinct elements
# index - next location in array
# num - given number
# reducednum - reduced number
def findcombinationsutil(arr, index, n, red_num):
# set to store all the
# distinct elements
s = set()
sum = 0
# base condition
if (red_num < 0):
return
if (red_num == 0):
# iterate over all the elements
# and store it into the set
for i in range(index):
s.add(arr[i])
# calculate the sum of all
# the elements of the set
for itr in s:
sum = sum (itr)
# compare whether the sum is equal to n or not,
# if it is equal to n print the numbers
if (sum == n):
for i in s:
print(i, end = " ")
print("\n", end = "")
return
# find previous number stored in the array
if (index == 0):
prev = 1
else:
prev = arr[index - 1]
for k in range(prev, n 1, 1):
# store all the numbers recursively
# into the arr[]
arr[index] = k
findcombinationsutil(arr, index 1,
n, red_num - k)
# function to find all the
# distinct combinations of n
def findcombinations(n):
a = [0 for i in range(n 1)]
findcombinationsutil(a, 0, n, n)
# driver code
if __name__ == '__main__':
n = 7
findcombinations(n)
# this code is contributed by surendra_gangwar
c
// c# implementation of the approach
using system;
using system.collections.generic;
class gfg
{
/* arr[] to store all the distinct elements
index - next location in array
num - given number
reducednum - reduced number */
static void findcombinationsutil(int []arr, int index,
int n, int red_num)
{
// set to store all the
// distinct elements
hashset s = new hashset();
int sum = 0;
// base condition
if (red_num < 0)
{
return;
}
if (red_num == 0)
{
// iterate over all the elements
// and store it into the set
for (int i = 0; i < index; i )
{
s.add(arr[i]);
}
// calculate the sum of all
// the elements of the set
foreach (int itr in s)
{
sum = sum itr;
}
// compare whether the sum is equal to n or not,
// if it is equal to n print the numbers
if (sum == n)
{
foreach (int i in s)
{
console.write(i " ");
}
console.writeline();
return;
}
}
// find previous number stored in the array
int prev = (index == 0) ? 1 : arr[index - 1];
for (int k = prev; k <= n; k )
{
// store all the numbers recursively
// into the arr[]
if(index < n)
{
arr[index] = k;
findcombinationsutil(arr, index 1,
n, red_num - k);
}
}
}
// function to find all the
// distinct combinations of n
static void findcombinations(int n)
{
int []a = new int[n];
findcombinationsutil(a, 0, n, n);
}
// driver code
public static void main(string []arr)
{
int n = 7;
findcombinations(n);
}
}
// this code contributed by rajput-ji
java 描述语言
output:
1 2 4
1 6
2 5
3 4
7
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
