Combination Sum II

class Solution {
public:
    vector<vector<int>> findCombinations(vector<int>& candidates, int target) {
        vector<vector<int>> combinations;
        vector<int> current;
        sort(candidates.begin(), candidates.end());
        search(combinations, current, candidates, target, 0);
        return combinations;
    }

private:
    void search(vector<vector<int>>& solutions, vector<int>& current,
                vector<int>& candidates, int remaining, int start) {
        if (remaining < 0)
            return;
        else if (remaining == 0) {
            solutions.push_back(current);
        } else {
            for (int i = start;
                 i < candidates.size() && remaining >= candidates[i]; i++) {
                if (i > start && candidates[i] == candidates[i - 1]) continue;
                current.push_back(candidates[i]);
                search(solutions, current, candidates,
                       remaining - candidates[i], i + 1);
                current.pop_back();
            }
        }
    }
};

The given C++ code defines a solution to the problem of finding all unique combinations of numbers that add up to a specific target sum. Each number in the input list can only be used once in the combination. Here's a concise summary of how the solution works:

• The primary function findCombinations prepares the data and initiates the recursive search by sorting the candidates list and declaring the vector structures for storing the current combination and all successful combinations.
• The recursive function search traverses through the candidates, exploring each number as a potential part of a combination. It ensures no number is reused in the same combination by managing the start index.
• Key controls include:
  • Immediately returning if the remaining target is less than zero, as further exploration would be pointless.
  • Adding the current combination to the solution if the remaining target is zero, signaling a successful combination.
  • Skipping over duplicates to ensure that only unique combinations are considered. This is achieved by checking if the current candidate is the same as the one before and skipping it if it is, provided it's not the start of the loop.
  • Exploring deeper by including the current number in the combination and recursively calling search with the reduced target (remaining - candidates[i]).

This approach effectively uses backtracking to explore all potential combinations and ensure duplicates are not processed, leveraging the sorted nature of the list. The use of vectors and recursive function calls allows for dynamic and efficient management of state during the search.

class Solution {

    public List<List<Integer>> findCombinations(int[] nums, int target) {
        List<List<Integer>> results = new LinkedList<>();
        Arrays.sort(nums);
        findResults(results, new ArrayList<>(), nums, target, 0);
        return results;
    }

    private void findResults(
        List<List<Integer>> res,
        List<Integer> currentCombination,
        int[] nums,
        int remaining,
        int start
    ) {
        if (remaining < 0) return;
        else if (remaining == 0) {
            res.add(new ArrayList<>(currentCombination));
        } else {
            for (int i = start; i < nums.length && remaining >= nums[i]; i++) {
                if (i > start && nums[i] == nums[i - 1]) continue;
                currentCombination.add(nums[i]);
                findResults(
                    res,
                    currentCombination,
                    nums,
                    remaining - nums[i],
                    i + 1
                );
                currentCombination.remove(currentCombination.size() - 1);
            }
        }
    }
}

The provided Java solution focuses on solving the "Combination Sum II" problem. The approach involves using backtracking to find combinations of numbers from an array that sum up to a specific target, ensuring no combinations are repeated if the combination has already been considered previously.

• Sorting the Input Array: Initially, the array of numbers is sorted. This step is crucial as it helps in easily skipping over duplicates and efficiently checking if a subset meets the target requirement without exceeding it.

• Backtracking Algorithm: The main method findCombinations initializes the results list and calls the recursive function findResults. Here, the algorithm explores each number in the sorted list, deciding whether to include it in the current combination or not:

  • If the current sum exceeds the target, the function returns immediately as further addition will only increase the sum.
  • If the current sum equals the target, the current combination is saved to the result list.
  • As it recursively explores, after adding a number to the current combination, it calls itself to explore the next number, ensuring that each number is used only once by increasing the index.
  • To handle duplicates efficiently, the function skips the current number if it's the same as the previous one in the loop, unless it's the start of the loop. This step prevents counting the same combination multiple times.

• Combination Removal: After the recursive call, the number is removed from the current combination list, allowing the function to explore other potential combinations with different numbers.

This technique effectively ensures that all possible combinations are considered without redundancy, using sorting and a careful iterative process to manage combinations and backtracking to explore all potential paths. The solution is particularly efficient for solving combination problems where the order of numbers does not matter and duplicates need to be avoided.

class Solution:
    def findCombinationSum(
        self, nums: List[int], sum_target: int
    ) -> List[List[int]]:
        def dfs(combinations, current_list, nums, remaining, start_index):
            if remaining < 0:
                return
            elif remaining == 0:
                combinations.append(current_list.copy())
            else:
                for j in range(start_index, len(nums)):
                    if j > start_index and nums[j] == nums[j - 1]:
                        continue
                    if remaining < nums[j]:
                        break
                    current_list.append(nums[j])
                    dfs(
                        combinations,
                        current_list,
                        nums,
                        remaining - nums[j],
                        j + 1,
                    )
                    current_list.pop()

        collected_results = []
        nums.sort()
        dfs(collected_results, [], nums, sum_target, 0)
        return collected_results

The given Python3 solution is developed for solving the "Combination Sum II" problem, which requires finding all unique combinations in a list where the candidate numbers sum to a target. The method implemented ensures that each number in the input list may only be used once in the combination.

• The function findCombinationSum accepts two arguments: nums, a list of candidate numbers, and sum_target, the target sum.
• The Utilize a nested helper function dfs (depth-first search) to explore possible combinations.
  • It checks if the current sum exceeds the target or if it matches exactly.
  • If the current sum matches the target, the current list of numbers is added to the result list.
  • Otherwise, iterate over the list starting from the start_index to avoid re-using elements.
  • The recursion ensures unique combinations by skipping consecutive duplicates and enforcing only one usage per element.

The solution first sorts the input list to facilitate the skipping of duplicates within the recursive function. It ensures that once a number is used in a specific position, it isn't considered again in the same recursive branch but can be reused in different branches. Finally, the collected combinations which meet the target sum are returned in a list of lists format.