✅ Combination Sum – Java Code
Copy code
Java
import [Link].*;
public class CombinationSum1 {
static void findCombinations(int index, int[] arr, int target,
ArrayList<Integer> list,
ArrayList<ArrayList<Integer>> result) {
// Base condition
if (index == [Link]) {
if (target == 0) {
[Link](new ArrayList<>(list));
}
return;
}
// Pick the element (can pick unlimited times)
if (arr[index] <= target) {
[Link](arr[index]);
findCombinations(index, arr, target - arr[index], list, result);
[Link]([Link]() - 1); // backtrack
}
// Not pick the element
findCombinations(index + 1, arr, target, list, result);
}
public static ArrayList<ArrayList<Integer>> combinationSum(int[] arr, int target) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
findCombinations(0, arr, target, new ArrayList<>(), result);
return result;
}
public static void main(String[] args) {
int[] arr = {2, 3, 6, 7};
int target = 7;
ArrayList<ArrayList<Integer>> ans = combinationSum(arr, target);
[Link](ans);
}
✅
}
Output
Copy code
[[2, 2, 3], [7]]
2. 📌 Problem: Combination Sum II
import [Link].*;
class Solution {
public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
[Link](candidates);
backtrack(0, candidates, target, new ArrayList<>(), result);
return result;
}
private static void backtrack(int index, int[] candidates, int target,
List<Integer> current, List<List<Integer>> result) {
if (target == 0) {
[Link](new ArrayList<>(current));
return;
}
for (int i = index; i < [Link]; i++) {
if (i > index && candidates[i] == candidates[i - 1])
continue;
if (candidates[i] > target)
break;
[Link](candidates[i]);
backtrack(i + 1, candidates, target - candidates[i], current, result);
[Link]([Link]() - 1);
}
}
❓
}
Input
candidates = [10,1,2,7,6,1,5]
✅
target = 8
Output
[1,1,6]
[1,2,5]
[1,7]
[2,6]
[Link] of all subsets
Given an array print all the sum of the subset generated from it, in the increasing order.
Examples
Input: N = 3, arr[] = {5,2,1}
Output: 0,1,2,3,5,6,7,8
Explanation: We have to find all the subset’s sum and print [Link] this case the generated
subsets are [ [], [1], [2], [2,1], [5], [5,1], [5,2]. [5,2,1],so the sums we get will be 0,1,2,3,5,6,7,8
✅ Recursive Approach
import [Link].*;
class Solution {
static void subsetSums(int index, int sum, int[] arr, List<Integer> result) {
if (index == [Link]) {
[Link](sum);
return;
}
subsetSums(index + 1, sum + arr[index], arr, result);
subsetSums(index + 1, sum, arr, result);
}
public static void main(String[] args) {
int[] arr = {5, 2, 1};
List<Integer> result = new ArrayList<>();
subsetSums(0, 0, arr, result);
[Link](result);
for (int val : result)
[Link](val + " ");
}
}
Input
N=3
arr = {5, 2, 1}
Output
01235678
✅ Bitmasking Approach
Java
import [Link].*;
class Solution {
public static void main(String[] args) {
int[] arr = {3, 1, 2};
int n = [Link];
List<Integer> result = new ArrayList<>();
for (int mask = 0; mask < (1 << n); mask++) {
int sum = 0;
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
sum += arr[i];
}
}
[Link](sum);
}
[Link](result);
for (int val : result)
[Link](val + " ");
}
}
Input
N=3
arr = {3, 1, 2}
01233456
[Link] - II | Print all the Unique Subsets
Problem Statement: Given an integer array nums, which can have duplicate entries, provide the
power set. Duplicate subsets cannot exist in the solution set. Return the answer in any sequence.
Brute Force Approach (Using Set)
Code (Java)
Copy code
Java
import [Link].*;
class Solution {
public static void main(String[] args) {
int[] nums = {1, 2, 2};
int n = [Link];
Set<List<Integer>> set = new HashSet<>();
for (int mask = 0; mask < (1 << n); mask++) {
List<Integer> subset = new ArrayList<>();
for (int i = 0; i < n; i++) {
if ((mask & (1 << i)) != 0) {
[Link](nums[i]);
}
}
[Link](subset);
[Link](subset);
}
[Link](set);
}
}
Input
Copy code
array = [1, 2, 2]
Output
Copy code
[[], [1], [1,2], [1,2,2], [2], [2,2]]
✅ Optimal Approach (Backtracking)
Code (Java)
Copy code
Java
import [Link].*;
class Solution {
static void subsets(int index, int[] nums, List<Integer> current, List<List<Integer>> result) {
[Link](new ArrayList<>(current));
for (int i = index; i < [Link]; i++) {
if (i > index && nums[i] == nums[i - 1])
continue;
[Link](nums[i]);
subsets(i + 1, nums, current, result);
[Link]([Link]() - 1);
}
}
public static void main(String[] args) {
int[] nums = {1, 2, 2};
[Link](nums);
List<List<Integer>> result = new ArrayList<>();
subsets(0, nums, new ArrayList<>(), result);
[Link](result);
}
}
Input
Copy code
array = [1, 2, 2]
Output
Copy code
[[], [1], [1,2], [1,2,2], [2], [2,2]]
[Link] Sum III (Optimal – Backtracking)
Code (Java)
Copy code
Java
import [Link].*;
class Solution {
static void backtrack(int start, int k, int n,
List<Integer> current,
List<List<Integer>> result) {
if (k == 0 && n == 0) {
[Link](new ArrayList<>(current));
return;
}
if (k == 0 || n < 0) return;
for (int i = start; i <= 9; i++) {
[Link](i);
backtrack(i + 1, k - 1, n - i, current, result);
[Link]([Link]() - 1);
}
}
public static void main(String[] args) {
int k = 3, n = 7;
List<List<Integer>> result = new ArrayList<>();
backtrack(1, k, n, new ArrayList<>(), result);
[Link](result);
}
}
Input
k=3
n=7
Output
[[1, 2, 4]]
6. Letter Combinations of a Phone Number
Code (Java)
Copy code
Java
import [Link].*;
class Solution {
static String[] map = {
"", "", "abc", "def", "ghi", "jkl",
"mno", "pqrs", "tuv", "wxyz"
};
static void backtrack(int index, String digits,
StringBuilder current,
List<String> result) {
if (index == [Link]()) {
[Link]([Link]());
return;
}
String letters = map[[Link](index) - '0'];
for (char ch : [Link]()) {
[Link](ch);
backtrack(index + 1, digits, current, result);
[Link]([Link]() - 1);
}
}
public static void main(String[] args) {
String digits = "34";
List<String> result = new ArrayList<>();
if ([Link]() != 0)
backtrack(0, digits, new StringBuilder(), result);
[Link](result);
}
}
Input
Copy code
digits = "34"
Output
Copy code
[dg, dh, di, eg, eh, ei, fg, fh, fi]