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.
What is the difficulty level of this exercise?
Test your Programming skills with w3resource's quiz.
- Weekly Trends
- Python Interview Questions and Answers: Comprehensive Guide
- Scala Exercises, Practice, Solution
- Kotlin Exercises practice with solution
- MongoDB Exercises, Practice, Solution
- SQL Exercises, Practice, Solution - JOINS
- Java Basic Programming Exercises
- SQL Subqueries
- Adventureworks Database Exercises
- C# Sharp Basic Exercises
- SQL COUNT() with distinct
- JavaScript String Exercises
- JavaScript HTML Form Validation
- Java Collection Exercises
- SQL COUNT() function
- SQL Inner Join