mirror of https://github.com/evanferrao/dsa
73 lines
1.8 KiB
Java
73 lines
1.8 KiB
Java
// https://leetcode.com/problems/combination-sum-ii/
|
|
i
|
|
mport java.util.*;
|
|
|
|
class CombinationTwo {
|
|
|
|
public static void findCombination(int currentIndex, List<Integer> ds, int candidates[], int target, List<List<Integer>> finalAnswer){
|
|
|
|
if (target == 0){
|
|
finalAnswer.add(new ArrayList<>(ds));
|
|
return;
|
|
}
|
|
|
|
for (int i = currentIndex; i < candidates.length; i++){
|
|
|
|
if (i > currentIndex && candidates[i] == candidates[i-1]) continue;
|
|
// or i != currentIndex would also work
|
|
|
|
if (candidates[i] > target) break;
|
|
|
|
ds.add(candidates[i]);
|
|
|
|
findCombination(i + 1, ds, candidates, target - candidates[i], finalAnswer);
|
|
|
|
ds.remove(ds.size() - 1);
|
|
}
|
|
}
|
|
|
|
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
|
|
|
|
Arrays.sort(candidates);
|
|
|
|
List<List<Integer>> finalAnswer = new ArrayList<>();
|
|
List<Integer> ds = new ArrayList<>();
|
|
|
|
findCombination(0, ds, candidates, target, finalAnswer);
|
|
|
|
return finalAnswer;
|
|
}
|
|
}
|
|
|
|
|
|
public class Main {
|
|
public static void main(String[] args) {
|
|
|
|
Scanner sc = new Scanner(System.in);
|
|
|
|
System.out.print("Enter number of elements: ");
|
|
int n = sc.nextInt();
|
|
|
|
int[] candidates = new int[n];
|
|
|
|
System.out.println("Enter elements:");
|
|
for(int i = 0; i < n; i++){
|
|
candidates[i] = sc.nextInt();
|
|
}
|
|
|
|
System.out.print("Enter target: ");
|
|
int target = sc.nextInt();
|
|
|
|
Solution obj = new Solution();
|
|
|
|
List<List<Integer>> result = obj.combinationSum2(candidates, target);
|
|
|
|
System.out.println("Unique combinations are:");
|
|
for(List<Integer> list : result){
|
|
System.out.println(list);
|
|
}
|
|
|
|
sc.close();
|
|
}
|
|
}
|