I am currently tackling the challenge of solving LeetCode #49 Combination Sum. The objective here is to identify all the distinct combinations that add up to the specified target.
While it's relatively straightforward to find permutations that result in the desired sum, I'm facing a hurdle in modifying my code to only generate unique permutations.
Can someone shed light on the fundamental concept in dynamic programming for obtaining unique results using recursion?
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum = function (candidates, target) {
let distinct = []
let dfs = (candidates, target, list = []) => {
if (target === 0) {
distinct.push(list)
return
}
candidates.forEach((candidate, i) => {
let diff = target - candidate;
if (diff >= 0) {
dfs(candidates, diff, [...list, candidate])
}
})
}
dfs(candidates, target)
return distinct
};
Input:
[2,3,6,7]
7
My Output:
[[2,2,3],[2,3,2],[3,2,2],[7]]
Desired Output:
[[2,2,3],[7]]
How can I prevent duplicate entries?