Java: Find all unique combinations from a collection of candidate numbers

Java Basic: Exercise-209 with Solution

Write a Java program to find all unique combinations from a collection of candidate numbers. The sum of the numbers will equal a given target number.

Sample Solution:

Java Code:

import java.util.*;
class Main {
 private static < K, V > void insert(Map < K, List < V >> hashMap, K key, V value) {
  if (!hashMap.containsKey(key)) {
   hashMap.put(key, new ArrayList < > ());
  }
  hashMap.get(key).add(value);
 }
 public static void Subsets(int[] A, int i, int j) {
  System.out.print("{ ");
  for (int k = i; k <= j; k++) {
   System.out.print(A[k] + " ");
  }
  System.out.println("}");
 }

 public static void Subsets(int[] A, int sum) {
  Map < Integer, List < Integer >> hashMap = new HashMap < > ();
  insert(hashMap, 0, -1);
  int sum_so_far = 0;
  for (int index = 0; index < A.length; index++) {

   sum_so_far += A[index];
   if (hashMap.containsKey(sum_so_far - sum)) {
    List < Integer > list = hashMap.get(sum_so_far - sum);
    for (Integer value: list) {
     Subsets(A, value + 1, index);
    }
   }
   insert(hashMap, sum_so_far, index);
  }
 }

 public static void main(String[] args) {
  {
   Scanner s = new Scanner(System.in);
   System.out.println("Input number of elements of the array: ");
   int n = s.nextInt();
   System.out.println("Input number format: 2 3 4 5: ");
   int arr[] = new int[n];
   System.out.println("Enter elements:");
   for (int i = 0; i < n; i++)
    arr[i] = s.nextInt();
   System.out.println("Enter target sum:");
   int sum = s.nextInt();
   int A[] = new int[arr.length];
   A = Arrays.copyOf(arr, arr.length);
   System.out.println("A solution set is:");
   Subsets(A, sum);
   System.exit(0);
  }
 }
}

Sample Output:

Input number of elements of the array: 
 3
Input number format: 2 3 4 5: 
Enter elements:
 6 7 8
Enter target sum:
 21
A solution set is:
{ 6 7 8 }

Pictorial Presentation:

Flowchart:

Java Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Java program to create a basic string compression method using the counts of repeated characters.
Next: Write a Java program to match any single character (use ?) or any sequence of characters use *) including the empty.