Description:
Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to target.
Each number in candidates may only be used once in the combination.
Note: The solution set must not contain duplicate combinations.
Examples:
Example 1:
Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:
Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]Solution in Python:
To solve this problem of finding all unique combinations in candidates where the candidate numbers sum to the target, we can use a backtracking approach. This will involve recursively exploring each potential combination of numbers to see if they add up to the target.
Python
from typing import List
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
def backtrack(start, target, path):
if target == 0:
result.append(path)
return
if target < 0:
return
for i in range(start, len(candidates)):
# Skip duplicates
if i > start and candidates[i] == candidates[i-1]:
continue
# Include the current number and move to the next
backtrack(i + 1, target - candidates[i], path + [candidates[i]])
candidates.sort()
result = []
backtrack(0, target, [])
return resultExplanation of the Code:
- Sorting: The
candidates.sort()line sorts the input list. This helps to easily skip over duplicate elements in the list. - Backtracking Function:
- The
backtrackfunction takes three parameters:start: The index to start from in the candidates list.target: The remaining sum we need to achieve.path: The current combination of numbers being considered.
- If
target == 0, it means we have found a valid combination, so we addpathto theresult. - If
target < 0, it means this path is not valid, so we return early.
- The
- Loop and Skip Duplicates:
- The for-loop iterates over the candidates starting from the
startindex. - The condition
if i > start and candidates[i] == candidates[i-1]ensures that we skip over duplicate numbers, which helps in avoiding duplicate combinations in the result.
- The for-loop iterates over the candidates starting from the
- Recursive Call:
- The recursive call
backtrack(i + 1, target - candidates[i], path + [candidates[i]])includes the current candidate in the path and moves the start index toi + 1to avoid reusing the same element.
- The recursive call
This approach ensures that all unique combinations that sum to the target are found without duplicates, adhering to the problem’s constraints.
Solution in Javascript:
JavaScript
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
const result = [];
// Sort the candidates array to handle duplicates easily
candidates.sort((a, b) => a - b);
/**
* Helper function to perform backtracking
* @param {number} start - The starting index for the current recursion
* @param {number} target - The remaining target sum
* @param {number[]} path - The current combination of numbers being considered
*/
function backtrack(start, target, path) {
if (target === 0) {
// If the target is met, add the current path to the result
result.push([...path]);
return;
}
if (target < 0) {
// If the target becomes negative, stop further exploration
return;
}
for (let i = start; i < candidates.length; i++) {
// Skip duplicates
if (i > start && candidates[i] === candidates[i - 1]) {
continue;
}
// Include the current candidate in the path and recurse
path.push(candidates[i]);
backtrack(i + 1, target - candidates[i], path);
path.pop(); // Remove the last candidate from the path to explore next possibilities
}
}
// Start backtracking with initial values
backtrack(0, target, []);
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>();
// Sort the candidates array to handle duplicates easily
Arrays.sort(candidates);
// Start backtracking with initial values
backtrack(candidates, target, 0, new ArrayList<>(), result);
return result;
}
/**
* Helper function to perform backtracking
* @param candidates - The sorted array of candidate numbers
* @param target - The remaining target sum
* @param start - The starting index for the current recursion
* @param path - The current combination of numbers being considered
* @param result - The list of all valid combinations found
*/
private void backtrack(int[] candidates, int target, int start, List<Integer> path, List<List<Integer>> result) {
if (target == 0) {
// If the target is met, add the current path to the result
result.add(new ArrayList<>(path));
return;
}
if (target < 0) {
// If the target becomes negative, stop further exploration
return;
}
for (int i = start; i < candidates.length; i++) {
// Skip duplicates
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
// Include the current candidate in the path and recurse
path.add(candidates[i]);
backtrack(candidates, target - candidates[i], i + 1, path, result);
path.remove(path.size() - 1); // Remove the last candidate from the path to explore next possibilities
}
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> CombinationSum2(int[] candidates, int target) {
IList<IList<int>> result = new List<IList<int>>();
// Sort the candidates array to handle duplicates easily
Array.Sort(candidates);
// Start backtracking with initial values
Backtrack(candidates, target, 0, new List<int>(), result);
return result;
}
/**
* Helper function to perform backtracking
* @param candidates - The sorted array of candidate numbers
* @param target - The remaining target sum
* @param start - The starting index for the current recursion
* @param path - The current combination of numbers being considered
* @param result - The list of all valid combinations found
*/
private void Backtrack(int[] candidates, int target, int start, IList<int> path, IList<IList<int>> result) {
if (target == 0) {
// If the target is met, add the current path to the result
result.Add(new List<int>(path));
return;
}
if (target < 0) {
// If the target becomes negative, stop further exploration
return;
}
for (int i = start; i < candidates.Length; i++) {
// Skip duplicates
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
// Include the current candidate in the path and recurse
path.Add(candidates[i]);
Backtrack(candidates, target - candidates[i], i + 1, path, result);
path.RemoveAt(path.Count - 1); // Remove the last candidate from the path to explore next possibilities
}
}
}