Posted on by Kalkicode
Code Backtracking

Print distinct combinations of given sum without repeating number

Here given code implementation process.

``````// C Program
// Print distinct combinations of given sum without repeating number
#include <stdio.h>

// This is use to display calculated result
void printResult(int result[], int sum)
{
printf("\n[");
for (int i = 0; i < sum; ++i)
{
if (result[i] == 1)
{
printf(" %d ", i + 1);
}
}
printf("]");
}
void printCombinations(int result[], int sum, int index, int k)
{
if (k == sum)
{
// When k is equal to given sum.
printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
for (int i = index; i >= 0; --i)
{
// Active result element
result[i] = 1;
// Find combinations using recursion
printCombinations(result, sum, i - 1, k + (i + 1));
// InActive result element
result[i] = 0;
}
}
void combinations(int sum)
{
if (sum <= 0)
{
return;
}
// Use to collect result
int result[sum];
// Provide initial value.
// Here zero indicates its not a part of result.
for (int i = 0; i < sum; ++i)
{
result[i] = 0;
}
// Test
printCombinations(result, sum, sum - 1, 0);
}
int main()
{
//Test Case
combinations(10);
return 0;
}``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````// Java Program
// Print distinct combinations of given sum without repeating number
class SumGroup
{
// This is use to display calculated result
public void printResult(int[] result, int sum)
{
System.out.print("\n[");
for (int i = 0; i < sum; ++i)
{
if (result[i] == 1)
{
System.out.print(" " + (i + 1) + " ");
}
}
System.out.print("]");
}
public void printCombinations(
int[] result,
int sum,
int index,
int k)
{
if (k == sum)
{
// When k is equal to given sum.
printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
for (int i = index; i >= 0; --i)
{
// Active result element
result[i] = 1;
// Find combinations using recursion
printCombinations(result, sum, i - 1, k + (i + 1));
// InActive result element
result[i] = 0;
}
}
public void combinations(int sum)
{
if (sum <= 0)
{
return;
}
// Use to collect result
int[] result = new int[sum];
// Provide initial value.
// Here zero indicates its not a part of result.
for (int i = 0; i < sum; ++i)
{
result[i] = 0;
}
// Test
printCombinations(result, sum, sum - 1, 0);
}
public static void main(String[] args)
{
// Test Case
}
}``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Print distinct combinations of given sum without repeating number
class SumGroup
{
public:
// This is use to display calculated result
void printResult(int result[], int sum)
{
cout << "\n[";
for (int i = 0; i < sum; ++i)
{
if (result[i] == 1)
{
cout << " " << (i + 1) << " ";
}
}
cout << "]";
}
void printCombinations(int result[], int sum, int index, int k)
{
if (k == sum)
{
// When k is equal to given sum.
this->printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
for (int i = index; i >= 0; --i)
{
// Active result element
result[i] = 1;
// Find combinations using recursion
this->printCombinations(result, sum, i - 1, k + (i + 1));
// InActive result element
result[i] = 0;
}
}
void combinations(int sum)
{
if (sum <= 0)
{
return;
}
// Use to collect result
int result[sum];
// Provide initial value.
// Here zero indicates its not a part of result.
for (int i = 0; i < sum; ++i)
{
result[i] = 0;
}
// Test
this->printCombinations(result, sum, sum - 1, 0);
}
};
int main()
{
// Test Case
return 0;
}``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````// Include namespace system
using System;
// Csharp Program
// Print distinct combinations of given sum without repeating number
public class SumGroup
{
// This is use to display calculated result
public void printResult(int[] result, int sum)
{
Console.Write("\n[");
for (int i = 0; i < sum; ++i)
{
if (result[i] == 1)
{
Console.Write(" " + (i + 1) + " ");
}
}
Console.Write("]");
}
public void printCombinations(
int[] result, int sum,
int index, int k)
{
if (k == sum)
{
// When k is equal to given sum.
this.printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
for (int i = index; i >= 0; --i)
{
// Active result element
result[i] = 1;
// Find combinations using recursion
this.printCombinations(result, sum,
i - 1, k + (i + 1));
// InActive result element
result[i] = 0;
}
}
public void combinations(int sum)
{
if (sum <= 0)
{
return;
}
// Use to collect result
int[] result = new int[sum];
// Provide initial value.
// Here zero indicates its not a part of result.
for (int i = 0; i < sum; ++i)
{
result[i] = 0;
}
// Test
this.printCombinations(result, sum, sum - 1, 0);
}
public static void Main(String[] args)
{
// Test Case
}
}``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````package main
import "fmt"
// Go Program
// Print distinct combinations of given sum without repeating number
type SumGroup struct {}
func getSumGroup() * SumGroup {
var me *SumGroup = &SumGroup {}
return me
}
// This is use to display calculated result
func(this SumGroup) printResult(result[] int,
sum int) {
fmt.Print("\n[")
for i := 0 ; i < sum ; i++ {
if result[i] == 1 {
fmt.Print(" ", (i + 1), " ")
}
}
fmt.Print("]")
}
func(this SumGroup) printCombinations(result[] int,
sum int, index int, k int) {
if k == sum {
// When k is equal to given sum.
this.printResult(result, sum)
return
} else if k > sum || index < 0 {
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return
}
for i := index ; i >= 0 ; i-- {
// Active result element
result[i] = 1
// Find combinations using recursion
this.printCombinations(result, sum,
i - 1, k + (i + 1))
// InActive result element
result[i] = 0
}
}
func(this SumGroup) combinations(sum int) {
if sum <= 0 {
return
}
// Use to collect result
var result = make([] int, sum)
// Provide initial value.
// Here zero indicates its not a part of result.
for i := 0 ; i < sum ; i++ {
result[i] = 0
}
// Test
this.printCombinations(result, sum, sum - 1, 0)
}
func main() {
var task * SumGroup = getSumGroup()
// Test Case
}``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````<?php
// Php Program
// Print distinct combinations of given sum without repeating number
class SumGroup
{
// This is use to display calculated result
public	function printResult(\$result, \$sum)
{
echo("\n[");
for (\$i = 0; \$i < \$sum; ++\$i)
{
if (\$result[\$i] == 1)
{
echo(" ".(\$i + 1).
" ");
}
}
echo("]");
}
public	function printCombinations(\$result, \$sum, \$index, \$k)
{
if (\$k == \$sum)
{
// When k is equal to given sum.
\$this->printResult(\$result, \$sum);
return;
}
else if (\$k > \$sum || \$index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
for (\$i = \$index; \$i >= 0; --\$i)
{
// Active result element
\$result[\$i] = 1;
// Find combinations using recursion
\$this->printCombinations(\$result, \$sum,
\$i - 1, \$k + (\$i + 1));
// InActive result element
\$result[\$i] = 0;
}
}
public	function combinations(\$sum)
{
if (\$sum <= 0)
{
return;
}
// Use to collect result
\$result = array_fill(0, \$sum, 0);
// Provide initial value.
// Here zero indicates its not a part of result.
for (\$i = 0; \$i < \$sum; ++\$i)
{
\$result[\$i] = 0;
}
// Test
\$this->printCombinations(\$result, \$sum, \$sum - 1, 0);
}
}

function main()
{
// Test Case
}
main();``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````// Node JS Program
// Print distinct combinations of given sum without repeating number
class SumGroup
{
// This is use to display calculated result
printResult(result, sum)
{
process.stdout.write("\n[");
for (var i = 0; i < sum; ++i)
{
if (result[i] == 1)
{
process.stdout.write(" " + (i + 1) + " ");
}
}
process.stdout.write("]");
}
printCombinations(result, sum, index, k)
{
if (k == sum)
{
// When k is equal to given sum.
this.printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
for (var i = index; i >= 0; --i)
{
// Active result element
result[i] = 1;
// Find combinations using recursion
this.printCombinations(result, sum, i - 1, k + (i + 1));
// InActive result element
result[i] = 0;
}
}
combinations(sum)
{
if (sum <= 0)
{
return;
}
// Use to collect result
var result = Array(sum).fill(0);
// Provide initial value.
// Here zero indicates its not a part of result.
for (var i = 0; i < sum; ++i)
{
result[i] = 0;
}
// Test
this.printCombinations(result, sum, sum - 1, 0);
}
}

function main()
{
// Test Case
}
main();``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````#  Python 3 Program
#  Print distinct combinations of given sum without repeating number
class SumGroup :
#  This is use to display calculated result
def printResult(self, result, sum) :
print("\n[", end = "")
i = 0
while (i < sum) :
if (result[i] == 1) :
print("", (i + 1) ,"", end = "")

i += 1

print("]", end = "")

def printCombinations(self, result, sum, index, k) :
if (k == sum) :
#  When k is equal to given sum.
self.printResult(result, sum)
return
elif (k > sum or index < 0) :
#  When k value is greater than given sum or
#  Index is less than zero.
#  Need to stop process.
return

i = index
while (i >= 0) :
#  Active result element
result[i] = 1
#  Find combinations using recursion
self.printCombinations(result, sum, i - 1, k + (i + 1))
#  InActive result element
result[i] = 0
i -= 1

def combinations(self, sum) :
if (sum <= 0) :
return

#  Use to collect result
result = [0] * (sum)
i = 0
#  Provide initial value.
#  Here zero indicates its not a part of result.
while (i < sum) :
result[i] = 0
i += 1

#  Test
self.printCombinations(result, sum, sum - 1, 0)

def main() :
#  Test Case

if __name__ == "__main__": main()``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````#  Ruby Program
#  Print distinct combinations of given sum without repeating number
class SumGroup
#  This is use to display calculated result
def printResult(result, sum)
print("\n[")
i = 0
while (i < sum)
if (result[i] == 1)
print(" ", (i + 1) ," ")
end

i += 1
end

print("]")
end

def printCombinations(result, sum, index, k)
if (k == sum)
#  When k is equal to given sum.
self.printResult(result, sum)
return
elsif (k > sum || index < 0)
#  When k value is greater than given sum or
#  Index is less than zero.
#  Need to stop process.
return
end

i = index
while (i >= 0)
#  Active result element
result[i] = 1
#  Find combinations using recursion
self.printCombinations(result, sum, i - 1, k + (i + 1))
#  InActive result element
result[i] = 0
i -= 1
end

end

def combinations(sum)
if (sum <= 0)
return
end

#  Use to collect result
result = Array.new(sum) {0}
i = 0
#  Provide initial value.
#  Here zero indicates its not a part of result.
while (i < sum)
result[i] = 0
i += 1
end

#  Test
self.printCombinations(result, sum, sum - 1, 0)
end

end

def main()
#  Test Case
end

main()``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````// Scala Program
// Print distinct combinations of given sum without repeating number
class SumGroup()
{
// This is use to display calculated result
def printResult(result: Array[Int], sum: Int): Unit = {
print("\n[");
var i: Int = 0;
while (i < sum)
{
if (result(i) == 1)
{
print(" " + (i + 1) + " ");
}
i += 1;
}
print("]");
}
def printCombinations(
result: Array[Int],
sum: Int, index: Int,
k: Int): Unit = {
if (k == sum)
{
// When k is equal to given sum.
printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
var i: Int = index;
while (i >= 0)
{
// Active result element
result(i) = 1;
// Find combinations using recursion
printCombinations(result, sum, i - 1, k + (i + 1));
// InActive result element
result(i) = 0;
i -= 1;
}
}
def combinations(sum: Int): Unit = {
if (sum <= 0)
{
return;
}
// Use to collect result
var result: Array[Int] = Array.fill[Int](sum)(0);
var i: Int = 0;
// Provide initial value.
// Here zero indicates its not a part of result.
while (i < sum)
{
result(i) = 0;
i += 1;
}
// Test
printCombinations(result, sum, sum - 1, 0);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SumGroup = new SumGroup();
// Test Case
}
}``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````// Swift 4 Program
// Print distinct combinations of given sum without repeating number
class SumGroup
{
// This is use to display calculated result
func printResult(_ result: [Int], _ sum: Int)
{
print("\n[", terminator: "");
var i: Int = 0;
while (i < sum)
{
if (result[i] == 1)
{
print("", (i + 1) ,"", terminator: "");
}
i += 1;
}
print("]", terminator: "");
}
func printCombinations(_ result: inout[Int],
_ sum: Int,
_ index: Int,
_ k: Int)
{
if (k == sum)
{
// When k is equal to given sum.
self.printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
var i: Int = index;
while (i >= 0)
{
// Active result element
result[i] = 1;
// Find combinations using recursion
self.printCombinations(&result, sum, i - 1, k + (i + 1));
// InActive result element
result[i] = 0;
i -= 1;
}
}
func combinations(_ sum: Int)
{
if (sum <= 0)
{
return;
}
// Use to collect result
var result: [Int] = Array(repeating: 0, count: sum);
var i: Int = 0;
// Provide initial value.
// Here zero indicates its not a part of result.
while (i < sum)
{
result[i] = 0;
i += 1;
}
// Test
self.printCombinations(&result, sum, sum - 1, 0);
}
}
func main()
{
// Test Case
}
main();``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````
``````// Kotlin Program
// Print distinct combinations of given sum without repeating number
class SumGroup
{
// This is use to display calculated result
fun printResult(result: Array < Int > , sum: Int): Unit
{
print("\n[");
var i: Int = 0;
while (i < sum)
{
if (result[i] == 1)
{
print(" " + (i + 1) + " ");
}
i += 1;
}
print("]");
}
fun printCombinations(
result: Array < Int > ,
sum: Int,
index: Int,
k: Int): Unit
{
if (k == sum)
{
// When k is equal to given sum.
this.printResult(result, sum);
return;
}
else if (k > sum || index < 0)
{
// When k value is greater than given sum or
// Index is less than zero.
// Need to stop process.
return;
}
var i: Int = index;
while (i >= 0)
{
// Active result element
result[i] = 1;
// Find combinations using recursion
this.printCombinations(result, sum, i - 1, k + (i + 1));
// InActive result element
result[i] = 0;
i -= 1;
}
}
fun combinations(sum: Int): Unit
{
if (sum <= 0)
{
return;
}
// Use to collect result
val result: Array < Int > = Array(sum)
{
0
};
var i: Int = 0;
// Provide initial value.
// Here zero indicates its not a part of result.
while (i < sum)
{
result[i] = 0;
i += 1;
}
// Test
this.printCombinations(result, sum, sum - 1, 0);
}
}
fun main(args: Array < String > ): Unit
{
// Test Case
}``````

Output

``````[ 10 ]
[ 1  9 ]
[ 2  8 ]
[ 3  7 ]
[ 1  2  7 ]
[ 4  6 ]
[ 1  3  6 ]
[ 1  4  5 ]
[ 2  3  5 ]
[ 1  2  3  4 ]``````

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post