Skip to main content

Find all distinct combinations of k sum in array

Here given code implementation process.

import java.util.Arrays;
import java.util.ArrayList;
/*
    Java Program for
    Find all distinct combinations of k sum in array
*/
public class Combinations
{
	public void printArray(int[] arr, int n)
	{
		System.out.print("\n Array : ");
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	public void printCombination(
      ArrayList < Integer > data, 
      ArrayList < String > result, 
      int index, 
      int count, 
      int k, 
      int sum, 
      String ans)
	{
		if (sum == k)
		{
			result.add(ans);
		}
		if (index >= data.size() || count > data.size())
		{
			return;
		}
		int i = index;
		while (i < data.size())
		{
			printCombination(data, 
                             result, i, 
                             count + 1, 
                             k, data.get(i) + sum, 
                             ans + " " + data.get(i));
			i++;
		}
	}
	public void distinctCombination(int[] arr, int n, int k)
	{
		if (n <= 0)
		{
			return;
		}
		printArray(arr, n);
		// First sort given array
		Arrays.sort(arr);
		// Auxiliary space 
		ArrayList < Integer > data = new ArrayList < Integer > ();
		ArrayList < String > result = new ArrayList < String > ();
		// Add first element
		data.add(arr[0]);
		// Collect all distinct elements
		for (int i = 1; i < n; ++i)
		{
			if (arr[i] != arr[i - 1])
			{
				data.add(arr[i]);
			}
		}
		// Print combinations
		printCombination(data, result, 0, 0, k, 0, "");
		System.out.print("\n Given k : " + k);
		System.out.print("\n Result : ");
		if (result.size() == 0)
		{
			// When k sum  not exist
			System.out.print(" None \n");
		}
		else
		{
			System.out.print("\n");
			// Display combination
			for (int i = 0; i < result.size(); ++i)
			{
				System.out.println(result.get(i));
			}
		}
	}
	public static void main(String[] args)
	{
		Combinations task = new Combinations();
		int[] arr1 = {
			5 , 2 , 2 , 1 , 6 , 3 , 4
		};
		int[] arr2 = {
			6 , -3 , 2 , 3 , 1 , 4 , 1
		};
		// Test A
		// Get the length of array
		int n = arr1.length;
		// Sum k
		int k = 7;
		// Test
		task.distinctCombination(arr1, n, k);
		// Test B
		// Get the length of array
		n = arr2.length;
		// Sum k
		k = -4;
		// Test
		task.distinctCombination(arr2, n, k);
	}
}

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
// Include header file
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
/*
    C++ Program for
    Find all distinct combinations of k sum in array
*/
class Combinations
{
	public: void printArray(int arr[], int n)
	{
		cout << "\n Array : ";
		for (int i = 0; i < n; ++i)
		{
			cout << " " << arr[i];
		}
	}
	void printCombination(
      vector < int > data, 
      vector < string > &result, 
      int index, 
      int count, 
      int k, 
      int sum, 
      string ans)
	{
		if (sum == k)
		{
			result.push_back(ans);
		}
		if (index >= data.size() || count > data.size())
		{
			return;
		}
		int i = index;
		while (i < data.size())
		{
			this->printCombination(
              data, result, i, 
              count + 1, k, 
              data.at(i) + sum, ans  +  " "
				 +  to_string(data.at(i))
            );
			i++;
		}
	}
	void distinctCombination(int arr[], int n, int k)
	{
		if (n <= 0)
		{
			return;
		}
		this->printArray(arr, n);
		// First sort given array
		sort(arr, arr + n);
		// Auxiliary space 
		vector < int > data;
		vector < string > result;
		// Add first element
		data.push_back(arr[0]);
		// Collect all distinct elements
		for (int i = 1; i < n; ++i)
		{
			if (arr[i] != arr[i - 1])
			{
				data.push_back(arr[i]);
			}
		}
		// Print combinations
		this->printCombination(data, result, 0, 0, k, 0, "");
		cout << "\n Given k : " << k;
		cout << "\n Result : ";
		if (result.size() == 0)
		{
			// When k sum  not exist
			cout << " None \n";
		}
		else
		{
			cout << "\n";
			// Display combination
			for (int i = 0; i < result.size(); ++i)
			{
				cout << result.at(i) << endl;
			}
		}
	}
};
int main()
{
	Combinations *task = new Combinations();
	int arr1[] = {
		5 , 2 , 2 , 1 , 6 , 3 , 4
	};
	int arr2[] = {
		6 , -3 , 2 , 3 , 1 , 4 , 1
	};
	// Test A
	// Get the length of array
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// Sum k
	int k = 7;
	// Test
	task->distinctCombination(arr1, n, k);
	// Test B
	// Get the length of array
	n = sizeof(arr2) / sizeof(arr2[0]);
	// Sum k
	k = -4;
	// Test
	task->distinctCombination(arr2, n, k);
	return 0;
}

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
// Include namespace system
using System;
using System.Collections.Generic;
/*
    Csharp Program for
    Find all distinct combinations of k sum in array
*/
public class Combinations
{
	public void printArray(int[] arr, int n)
	{
		Console.Write("\n Array : ");
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	public void printCombination(
      List < int > data, List < string > result, 
      int index, int count, 
      int k, int sum, String ans)
	{
		if (sum == k)
		{
			result.Add(ans);
		}
		if (index >= data.Count || count > data.Count)
		{
			return;
		}
		int i = index;
		while (i < data.Count)
		{
			this.printCombination(
              data, result, i, count + 1, 
              k, data[i] + sum, ans + " " + data[i]);
			i++;
		}
	}
	public void distinctCombination(int[] arr, int n, int k)
	{
		if (n <= 0)
		{
			return;
		}
		this.printArray(arr, n);
		// First sort given array
		Array.Sort(arr);
		// Auxiliary space 
		List < int > data = new List < int > ();
		List < string > result = new List < string > ();
		// Add first element
		data.Add(arr[0]);
		// Collect all distinct elements
		for (int i = 1; i < n; ++i)
		{
			if (arr[i] != arr[i - 1])
			{
				data.Add(arr[i]);
			}
		}
		// Print combinations
		this.printCombination(data, result, 0, 0, k, 0, "");
		Console.Write("\n Given k : " + k);
		Console.Write("\n Result : ");
		if (result.Count == 0)
		{
			// When k sum  not exist
			Console.Write(" None \n");
		}
		else
		{
			Console.Write("\n");
			// Display combination
			for (int i = 0; i < result.Count; ++i)
			{
				Console.WriteLine(result[i]);
			}
		}
	}
	public static void Main(String[] args)
	{
		Combinations task = new Combinations();
		int[] arr1 = {
			5 , 2 , 2 , 1 , 6 , 3 , 4
		};
		int[] arr2 = {
			6 , -3 , 2 , 3 , 1 , 4 , 1
		};
		// Test A
		// Get the length of array
		int n = arr1.Length;
		// Sum k
		int k = 7;
		// Test
		task.distinctCombination(arr1, n, k);
		// Test B
		// Get the length of array
		n = arr2.Length;
		// Sum k
		k = -4;
		// Test
		task.distinctCombination(arr2, n, k);
	}
}

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
package main
import "strconv"
import "sort"
import "fmt"
/*
    Go Program for
    Find all distinct combinations of k sum in array
*/
type Combinations struct { result bool}
func getCombinations() * Combinations {
	var me *Combinations = &Combinations {}
	me.result = false
	return me
}
func(this Combinations) printArray(arr[] int, n int) {
	fmt.Print("\n Array : ")
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
func(this Combinations) printCombination(data []int, index int, count int, k int, sum int, ans string) {
	if sum == k {
		fmt.Print(ans,"\n");
	
	}
	if index >= len(data) || count > len(data) {
		return
	}
	var i int = index
	for (i < len(data)) {
		this.printCombination(data, i, count + 1, 
			k, data[i] + sum, ans + " " + strconv.Itoa(data[i]))
		i++
	}
}
func(this Combinations) distinctCombination(arr[] int, n int, k int) {
	if n <= 0 {
		return
	}
	this.printArray(arr, n)
	// First sort given array
	sort.Ints(arr)
	// Auxiliary space 
	var data = make([]int, 0)
	this.result = false
	// Add first element
	data = append(data, arr[0])
	// Collect all distinct elements
	for i := 1 ; i < n ; i++ {
		if arr[i] != arr[i - 1] {
			data = append(data, arr[i])
		}
	}
	fmt.Print("\n Given k : ", k)
	fmt.Print("\n Result : ")
	// Print combinations
	this.printCombination(data, 0, 0, k, 0, "")

	if this.result == true {
		// When k sum  not exist
		fmt.Print(" None \n")
	} 
}
func main() {
	var task * Combinations = getCombinations()
	var arr1 = [] int { 5 , 2 , 2 , 1 , 6 , 3 , 4 }
	var arr2 = [] int { 6 , -3 , 2 , 3 , 1 , 4 , 1 }
	// Test A
	// Get the length of array
	var n int = len(arr1)
	// Sum k
	var k int = 7
	// Test
	task.distinctCombination(arr1, n, k)
	// Test B
	// Get the length of array
	n = len(arr2)
	// Sum k
	k = -4
	// Test
	task.distinctCombination(arr2, n, k)
}

Output

Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :  1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :  -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2

<?php
/*
    Php Program for
    Find all distinct combinations of k sum in array
*/
class Combinations
{
	public	function printArray($arr, $n)
	{
		echo("\n Array : ");
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
	public	function printCombination(
  		$data, &$result, $index, 
   		$count, $k, $sum, $ans)
	{
		if ($sum == $k)
		{
			$result[] = $ans;
		}
		if ($index >= count($data) || $count > count($data))
		{
			return;
		}
		$i = $index;
		while ($i < count($data))
		{
			$this->printCombination(
              $data, $result, $i, 
              $count + 1, $k, 
              $data[$i] + $sum, $ans." ".strval($data[$i]));
			$i++;
		}
	}
	public	function distinctCombination($arr, $n, $k)
	{
		if ($n <= 0)
		{
			return;
		}
		$this->printArray($arr, $n);
		// First sort given array
		sort($arr);
		// Auxiliary space 
		$data = array();
		$result = array();
		// Add first element
		$data[] = $arr[0];
		// Collect all distinct elements
		for ($i = 1; $i < $n; ++$i)
		{
			if ($arr[$i] != $arr[$i - 1])
			{
				$data[] = $arr[$i];
			}
		}
		// Print combinations
		$this->printCombination($data, $result, 0, 0, $k, 0, "");
		echo("\n Given k : ".$k);
		echo("\n Result : ");
		if (count($result) == 0)
		{
			// When k sum  not exist
			echo(" None \n");
		}
		else
		{
			echo("\n");
			// Display combination
			for ($i = 0; $i < count($result); ++$i)
			{
				echo($result[$i]."\n");
			}
		}
	}
}

function main()
{
	$task = new Combinations();
	$arr1 = array(5, 2, 2, 1, 6, 3, 4);
	$arr2 = array(6, -3, 2, 3, 1, 4, 1);
	// Test A
	// Get the length of array
	$n = count($arr1);
	// Sum k
	$k = 7;
	// Test
	$task->distinctCombination($arr1, $n, $k);
	// Test B
	// Get the length of array
	$n = count($arr2);
	// Sum k
	$k = -4;
	// Test
	$task->distinctCombination($arr2, $n, $k);
}
main();

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
/*
    Node JS Program for
    Find all distinct combinations of k sum in array
*/
class Combinations
{
	printArray(arr, n)
	{
		process.stdout.write("\n Array : ");
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	printCombination(data, result, index, count, k, sum, ans)
	{
		if (sum == k)
		{
			result.push(ans);
		}
		if (index >= data.length || count > data.length)
		{
			return;
		}
		var i = index;
		while (i < data.length)
		{
			this.printCombination(
              data, result, i, count + 1, k, 
              data[i] + sum, ans + " " + data[i]);
			i++;
		}
	}
	distinctCombination(arr, n, k)
	{
		if (n <= 0)
		{
			return;
		}
		this.printArray(arr, n);
		// First sort given array
		arr.sort(function(a, b)
		{
			return a - b;
		});
		// Auxiliary space 
		var data = [];
		var result = [];
		// Add first element
		data.push(arr[0]);
		// Collect all distinct elements
		for (var i = 1; i < n; ++i)
		{
			if (arr[i] != arr[i - 1])
			{
				data.push(arr[i]);
			}
		}
		// Print combinations
		this.printCombination(data, result, 0, 0, k, 0, "");
		process.stdout.write("\n Given k : " + k);
		process.stdout.write("\n Result : ");
		if (result.length == 0)
		{
			// When k sum  not exist
			process.stdout.write(" None \n");
		}
		else
		{
			process.stdout.write("\n");
			// Display combination
			for (var i = 0; i < result.length; ++i)
			{
				console.log(result[i]);
			}
		}
	}
}

function main()
{
	var task = new Combinations();
	var arr1 = [5, 2, 2, 1, 6, 3, 4];
	var arr2 = [6, -3, 2, 3, 1, 4, 1];
	// Test A
	// Get the length of array
	var n = arr1.length;
	// Sum k
	var k = 7;
	// Test
	task.distinctCombination(arr1, n, k);
	// Test B
	// Get the length of array
	n = arr2.length;
	// Sum k
	k = -4;
	// Test
	task.distinctCombination(arr2, n, k);
}
main();

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
#    Python 3 Program for
#    Find all distinct combinations of k sum in array
class Combinations :
	def printArray(self, arr, n) :
		print("\n Array : ", end = "")
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	def printCombination(self, data, result, 
                         index, count, k, sum, ans) :
		if (sum == k) :
			result.append(ans)
		
		if (index >= len(data) or count > len(data)) :
			return
		
		i = index
		while (i < len(data)) :
			self.printCombination(data, result, 
                                  i, count + 1, k, 
                                  data[i] + sum, ans + " " + str(data[i]))
			i += 1
		
	
	def distinctCombination(self, arr, n, k) :
		if (n <= 0) :
			return
		
		self.printArray(arr, n)
		#  First sort given list
		arr.sort()
		#  Auxiliary space 
		data = []
		result = []
		#  Add first element
		data.append(arr[0])
		i = 1
		#  Collect all distinct elements
		while (i < n) :
			if (arr[i] != arr[i - 1]) :
				data.append(arr[i])
			
			i += 1
		
		#  Print combinations
		self.printCombination(data, result, 0, 0, k, 0, "")
		print("\n Given k : ", k, end = "")
		print("\n Result : ", end = "")
		if (len(result) == 0) :
			#  When k sum  not exist
			print(" None ")
		else :
			print(end = "\n")
			i = 0
			#  Display combination
			while (i < len(result)) :
				print(result[i])
				i += 1
			
		
	

def main() :
	task = Combinations()
	arr1 = [5, 2, 2, 1, 6, 3, 4]
	arr2 = [6, -3, 2, 3, 1, 4, 1]
	#  Test A
	#  Get the length of list
	n = len(arr1)
	#  Sum k
	k = 7
	#  Test
	task.distinctCombination(arr1, n, k)
	#  Test B
	#  Get the length of list
	n = len(arr2)
	#  Sum k
	k = -4
	#  Test
	task.distinctCombination(arr2, n, k)

if __name__ == "__main__": main()

Output

 Array :   5  2  2  1  6  3  4
 Given k :  7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :   6  -3  2  3  1  4  1
 Given k :  -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
#    Ruby Program for
#    Find all distinct combinations of k sum in array
class Combinations 
	def printArray(arr, n) 
		print("\n Array : ")
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	def printCombination(data, result, index, count, k, sum, ans) 
		if (sum == k) 
			result.push(ans)
		end

		if (index >= data.length || count > data.length) 
			return
		end

		i = index
		while (i < data.length) 
			self.printCombination(data, result, i, 
                  count + 1, k, 
                  data[i] + sum, ans + " " + data[i].to_s)
			i += 1
		end

	end

	def distinctCombination(arr, n, k) 
		if (n <= 0) 
			return
		end

		self.printArray(arr, n)
		#  First sort given array
		arr = arr.sort
		#  Auxiliary space 
		data = []
		result = []
		#  Add first element
		data.push(arr[0])
		i = 1
		#  Collect all distinct elements
		while (i < n) 
			if (arr[i] != arr[i - 1]) 
				data.push(arr[i])
			end
			i += 1
		end

		#  Print combinations
		self.printCombination(data, result, 0, 0, k, 0, "")
		print("\n Given k : ", k)
		print("\n Result : ")
		if (result.length == 0) 
			#  When k sum  not exist
			print(" None \n")
		else
 
			print("\n")
			i = 0
			#  Display combination
			while (i < result.length) 
				print(result[i], "\n")
				i += 1
			end

		end

	end

end

def main() 
	task = Combinations.new()
	arr1 = [5, 2, 2, 1, 6, 3, 4]
	arr2 = [6, -3, 2, 3, 1, 4, 1]
	#  Test A
	#  Get the length of array
	n = arr1.length
	#  Sum k
	k = 7
	#  Test
	task.distinctCombination(arr1, n, k)
	#  Test B
	#  Get the length of array
	n = arr2.length
	#  Sum k
	k = -4
	#  Test
	task.distinctCombination(arr2, n, k)
end

main()

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result : 
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result : 
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2

import scala.collection.mutable._;
/*
    Scala Program for
    Find all distinct combinations of k sum in array
*/
class Combinations()
{
	def printArray(arr: Array[Int], n: Int): Unit = {
		print("\n Array : ");
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	def printCombination(
      data: ArrayBuffer[Int], 
      result: ArrayBuffer[String], 
        index: Int, count: Int, 
          k: Int, sum: Int, 
            ans: String): Unit = {
		if (sum == k)
		{
			result += ans;
		}
		if (index >= data.size || count > data.size)
		{
			return;
		}
		var i: Int = index;
		while (i < data.size)
		{
			printCombination(data, result, i, 
                             count + 1, k, data(i) + sum, 
                             ans + " " + data(i).toString());
			i += 1;
		}
	}
	def distinctCombination(arr: Array[Int], n: Int, k: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		printArray(arr, n);
		// First sort given array
		arr.sorted;
		// Auxiliary space 
		var data: ArrayBuffer[Int] = new ArrayBuffer[Int]();
		var result: ArrayBuffer[String] = new ArrayBuffer[String]();
		// Add first element
		data += arr(0);
		var i: Int = 1;
		// Collect all distinct elements
		while (i < n)
		{
			if (arr(i) != arr(i - 1))
			{
				data += arr(i);
			}
			i += 1;
		}
		// Print combinations
		printCombination(data, result, 0, 0, k, 0, "");
		print("\n Given k : " + k);
		print("\n Result : ");
		if (result.size == 0)
		{
			// When k sum  not exist
			print(" None \n");
		}
		else
		{
			print("\n");
			var i: Int = 0;
			// Display combination
			while (i < result.size)
			{
				println(result(i));
				i += 1;
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Combinations = new Combinations();
		var arr1: Array[Int] = Array(5, 2, 2, 1, 6, 3, 4);
		var arr2: Array[Int] = Array(6, -3, 2, 3, 1, 4, 1);
		// Test A
		// Get the length of array
		var n: Int = arr1.length;
		// Sum k
		var k: Int = 7;
		// Test
		task.distinctCombination(arr1, n, k);
		// Test B
		// Get the length of array
		n = arr2.length;
		// Sum k
		k = -4;
		// Test
		task.distinctCombination(arr2, n, k);
	}
}

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :
 5 2
 5 1 1
 2 2 2 1
 2 2 1 1 1
 2 2 3
 2 1 1 1 1 1
 2 1 1 3
 2 1 4
 1 1 1 1 1 1 1
 1 1 1 1 3
 1 1 1 4
 1 6
 1 3 3
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :
 6 -3 -3 -3 -3 -3 2 3
 6 -3 -3 -3 -3 -3 1 4
 6 -3 -3 -3 -3 -3 4 1
 6 -3 -3 -3 -3 2
 6 -3 -3 -3 -3 1 1
 6 -3 -3 -3 -3 1 1
 6 -3 -3 -3 -3 1 1
 -3 -3 -3 -3 -3 3 4 4
 -3 -3 -3 -3 2 2 2 2
 -3 -3 -3 -3 2 2 3 1
 -3 -3 -3 -3 2 2 3 1
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 1 1 4
 -3 -3 -3 -3 2 1 4 1
 -3 -3 -3 -3 2 4 1 1
 -3 -3 -3 -3 3 3 1 1
 -3 -3 -3 -3 3 3 1 1
 -3 -3 -3 -3 3 3 1 1
 -3 -3 -3 -3 3 1 4
 -3 -3 -3 -3 3 4 1
 -3 -3 -3 -3 4 4
 -3 -3 -3 2 2 1
 -3 -3 -3 2 2 1
 -3 -3 -3 2 3
 -3 -3 -3 2 1 1 1
 -3 -3 -3 2 1 1 1
 -3 -3 -3 2 1 1 1
 -3 -3 -3 2 1 1 1
 -3 -3 -3 3 1 1
 -3 -3 -3 3 1 1
 -3 -3 -3 3 1 1
 -3 -3 -3 1 1 1 1 1
 -3 -3 -3 1 1 1 1 1
 -3 -3 -3 1 1 1 1 1
 -3 -3 -3 1 1 1 1 1
 -3 -3 -3 1 4
 -3 -3 -3 1 1 1 1 1
 -3 -3 -3 4 1
 -3 -3 -3 1 1 1 1 1
 -3 -3 2
 -3 -3 1 1
 -3 -3 1 1
 -3 -3 1 1
import Foundation;
/*
    Swift 4 Program for
    Find all distinct combinations of k sum in array
*/
class Combinations
{
	func printArray(_ arr: [Int], _ n: Int)
	{
		print("\n Array : ", terminator: "");
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	func printCombination(
      _ data: [Int], 
      _ result: inout[String], 
        _ index: Int, 
          _ count: Int, 
            _ k: Int, 
              _ sum: Int, 
                _ ans: String)
	{
		if (sum == k)
		{
			result.append(ans);
		}
		if (index >= data.count || count > data.count)
		{
			return;
		}
		var i: Int = index;
		while (i < data.count)
		{
			self.printCombination(
              data, &result, i, count + 1, 
              k, data[i] + sum, ans + " " + String(data[i]));
			i += 1;
		}
	}
	func distinctCombination(_ arr: [Int], _ n: Int, _ k: Int)
	{
		if (n <= 0)
		{
			return;
		}
		self.printArray(arr, n);
		// First sort given array
		var value = arr.sorted();
		// Auxiliary space 
		var data: [Int] = [Int]();
		var result: [String] = [String]();
		// Add first element
		data.append(value[0]);
		var i: Int = 1;
		// Collect all distinct elements
		while (i < n)
		{
			if (value[i]  != value[i - 1])
			{
				data.append(value[i]);
			}
			i += 1;
		}
		// Print combinations
		self.printCombination(data, &result, 0, 0, k, 0, "");
		print("\n Given k : ", k, terminator: "");
		print("\n Result : ", terminator: "");
		if (result.count == 0)
		{
			// When k sum  not exist
			print(" None ");
		}
		else
		{
			print(terminator: "\n");
			var i: Int = 0;
			// Display combination
			while (i < result.count)
			{
				print(result[i]);
				i += 1;
			}
		}
	}
}
func main()
{
	let task: Combinations = Combinations();
	let arr1: [Int] = [5, 2, 2, 1, 6, 3, 4];
	let arr2: [Int] = [6, -3, 2, 3, 1, 4, 1];
	// Test A
	// Get the length of array
	var n: Int = arr1.count;
	// Sum k
	var k: Int = 7;
	// Test
	task.distinctCombination(arr1, n, k);
	// Test B
	// Get the length of array
	n = arr2.count;
	// Sum k
	k = -4;
	// Test
	task.distinctCombination(arr2, n, k);
}
main();

Output

 Array :   5  2  2  1  6  3  4
 Given k :  7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :   6  -3  2  3  1  4  1
 Given k :  -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
/*
    Kotlin Program for
    Find all distinct combinations of k sum in array
*/
class Combinations
{
	fun printArray(arr: Array < Int > , n: Int): Unit
	{
		print("\n Array : ");
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	fun printCombination(
      data: MutableList < Int >  , 
      result : MutableList < String >  , 
      index : Int, count: Int, 
      k: Int, sum: Int, 
      ans: String): Unit
	{
		if (sum == k)
		{
			result.add(ans);
		}
		if (index >= data.size || count > data.size)
		{
			return;
		}
		var i: Int = index;
		while (i < data.size)
		{
			this.printCombination(
              data, result, i, 
              count + 1, k, 
              data[i] + sum, 
              ans + " " + data[i].toString());
			i += 1;
		}
	}
	fun distinctCombination(arr: Array < Int > , n: Int, k: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		this.printArray(arr, n);
		// First sort given array
		arr.sort();
		// Auxiliary space 
		var data: MutableList < Int > = mutableListOf < Int > ();
		var result: MutableList < String > = mutableListOf < String > ();
		// Add first element
		data.add(arr[0]);
		var i: Int = 1;
		// Collect all distinct elements
		while (i < n)
		{
			if (arr[i] != arr[i - 1])
			{
				data.add(arr[i]);
			}
			i += 1;
		}
		// Print combinations
		this.printCombination(data, result, 0, 0, k, 0, "");
		print("\n Given k : " + k);
		print("\n Result : ");
		if (result.size == 0)
		{
			// When k sum  not exist
			print(" None \n");
		}
		else
		{
			print("\n");
			i = 0;
			// Display combination
			while (i < result.size)
			{
				println(result[i]);
				i += 1;
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Combinations = Combinations();
	val arr1: Array < Int > = arrayOf(5, 2, 2, 1, 6, 3, 4);
	val arr2: Array < Int > = arrayOf(6, -3, 2, 3, 1, 4, 1);
	// Test A
	// Get the length of array
	var n: Int = arr1.count();
	// Sum k
	var k: Int = 7;
	// Test
	task.distinctCombination(arr1, n, k);
	// Test B
	// Get the length of array
	n = arr2.count();
	// Sum k
	k = -4;
	// Test
	task.distinctCombination(arr2, n, k);
}

Output

 Array :  5 2 2 1 6 3 4
 Given k : 7
 Result :
 1 1 1 1 1 1 1
 1 1 1 1 1 2
 1 1 1 1 3
 1 1 1 2 2
 1 1 1 4
 1 1 2 3
 1 1 5
 1 2 2 2
 1 2 4
 1 3 3
 1 6
 2 2 3
 2 5
 3 4

 Array :  6 -3 2 3 1 4 1
 Given k : -4
 Result :
 -3 -3 -3 -3 1 1 6
 -3 -3 -3 -3 1 3 4
 -3 -3 -3 -3 2 2 4
 -3 -3 -3 -3 2 3 3
 -3 -3 -3 -3 2 6
 -3 -3 -3 -3 4 4
 -3 -3 -3 1 1 1 2
 -3 -3 -3 1 1 3
 -3 -3 -3 1 2 2
 -3 -3 -3 1 4
 -3 -3 -3 2 3
 -3 -3 1 1
 -3 -3 2
Last updated on by Kalkicode




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.

New Comment