Combination Sum II

import java.util.*;

class Solution {

    // Recursive helper function to find combinations
    private void func(int ind, int sum, List<Integer> nums, 
                      int[] candidates, List<List<Integer>> ans) {
        // If the sum is zero, add the current combination to the result
        if (sum == 0) {
            ans.add(new ArrayList<>(nums));
            return;
        }

        // If the sum is negative or we have exhausted the candidates, return
        if (sum < 0 || ind == candidates.length) return; 

        // Include the current candidate
        nums.add(candidates[ind]);

        // Recursively call with updated sum and next index
        func(ind + 1, sum - candidates[ind], nums, candidates, ans);

        // Backtrack by removing the last added candidate
        nums.remove(nums.size() - 1);

        // Skip duplicates: if not picking the current candidate, 
        // ensure the next candidate is different
        for(int i = ind + 1; i < candidates.length; i++) {
            if(candidates[i] != candidates[ind]) {
                func(i, sum, nums, candidates, ans);
                break;
            }
        }
    }

    // Main function to find all unique combinations
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> nums = new ArrayList<>();

        // Sort candidates to handle duplicates
        Arrays.sort(candidates);

        // Start the recursive process
        func(0, target, nums, candidates, ans);
        return ans;
    }
}

class Main {
    public static void main(String[] args) {
        Solution sol = new Solution();

        // Sample input
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;

        // Call the combinationSum2 function
        List<List<Integer>> result = sol.combinationSum2(candidates, target);

        // Output the result
        System.out.println("Combinations are: ");
        for (List<Integer> combination : result) {
            for (int num : combination) {
                System.out.print(num + " ");
            }
            System.out.println();
        }
    }
}

class Solution:
    def __init__(self):
        self.ans = []
    
    def func(self, ind, sum, nums, candidates):
        # If the sum is zero, add the current combination to the result
        if sum == 0:
            self.ans.append(nums[:])
            return
        
        # If the sum is negative or we have exhausted the candidates, return
        if sum < 0 or ind == len(candidates):
            return
        
        # Include the current candidate
        nums.append(candidates[ind])
        
        # Recursively call with updated sum and next index
        self.func(ind + 1, sum - candidates[ind], nums, candidates)
        
        # Backtrack by removing the last added candidate
        nums.pop()
        
        # Skip duplicates: if not picking the current candidate, 
        # ensure the next candidate is different
        for i in range(ind + 1, len(candidates)):
            if candidates[i] != candidates[ind]:
                self.func(i, sum, nums, candidates)
                break

    def combinationSum2(self, candidates, target):
        candidates.sort()  # Sort candidates to handle duplicates
        self.ans = []
        self.func(0, target, [], candidates)
        return self.ans


if __name__ == "__main__":
    sol = Solution()
    candidates = [10, 1, 2, 7, 6, 1, 5]
    target = 8
    result = sol.combinationSum2(candidates, target)

    print("Combinations are: ")
    for combination in result:
        print(combination)

class Solution {
    constructor() {
        this.ans = [];
    }

    func(ind, sum, nums, candidates) {
        // If the sum is zero, add the current combination to the result
        if (sum === 0) {
            this.ans.push([...nums]);
            return;
        }

        // If the sum is negative or we have exhausted the candidates, return
        if (sum < 0 || ind === candidates.length) return;

        // Include the current candidate
        nums.push(candidates[ind]);

        // Recursively call with updated sum and next index
        this.func(ind + 1, sum - candidates[ind], nums, candidates);

        // Backtrack by removing the last added candidate
        nums.pop();

        // Skip duplicates: if not picking the current candidate, 
        // ensure the next candidate is different
        for (let i = ind + 1; i < candidates.length; i++) {
            if (candidates[i] !== candidates[ind]) {
                this.func(i, sum, nums, candidates);
                break;
            }
        }
    }

    combinationSum2(candidates, target) {
        candidates.sort((a, b) => a - b); // Sort candidates to handle duplicates
        this.ans = [];
        this.func(0, target, [], candidates);
        return this.ans;
    }
}

// Main method for testing the Solution class
const sol = new Solution();
const candidates = [10, 1, 2, 7, 6, 1, 5];
const target = 8;
const result = sol.combinationSum2(candidates, target);

console.log("Combinations are: ");
result.forEach(combination => {
    console.log(combination);
});