Estoy resolviendo LeetCode #49 Combination Sum . La idea es encontrar todas las combinaciones únicas que suman al objetivo.
Es bastante sencillo encontrar las permutaciones que se suman a la suma, pero me cuesta modificar mi código para encontrar solo permutaciones únicas.
¿Cuál es el concepto general en programación dinámica para obtener resultados únicos con recursividad?
/** * @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 };Aporte:
[2,3,6,7] 7Mi salida:
[[2,2,3],[2,3,2],[3,2,2],[7]]Salida deseada:
[[2,2,3],[7]]¿Cómo evito los duplicados?
Una forma sencilla de manejar esto es dividir la recursividad en dos casos, uno en el que usamos el primer candidato y otro en el que no. En el primer caso, reducimos el total que necesitamos alcanzar. En el segundo, achicamos el número de candidatos disponibles. Eso significa que necesitamos al menos dos casos base, cuando el total es cero y cuando el número de candidatos llega a cero (aquí también manejamos el caso donde el total es menor que cero). Luego, las llamadas recursivas se vuelven bastante limpias:
const combos = (cs, t) => cs .length == 0 || t < 0 ? [] : t == 0 ? [[]] : [ ... combos (cs, t - cs [0]) .map (sub => [cs [0], ...sub]), // use cs [0] ... combos (cs .slice (1), t) // don't use it ] const display = (cs, t) => console .log (`combos (${JSON.stringify(cs)}, ${t}) => ${JSON.stringify(combos(cs, t))} `) display ([2, 3, 6, 7], 7) display ([2, 3, 5], 8) display ([8, 6, 7], 42)Necesita un index para asegurarse de que la misma combinación (orden diferente) no se repita nuevamente y comience su ciclo desde el índice.
let dfs = (candidates, target, list = [], index = 0) => {Este índice debe pasarse dentro de su función recursiva (lo he cambiado a bucle for para que sea más legible)
for (let i = index; i < candidates.length; i++) { ...... dfs(candidates, diff, [...list, candidates[i]], i)Código de trabajo a continuación :
var combinationSum = function(candidates, target) { let distinct = [] // add index in your function let dfs = (candidates, target, list = [], index = 0) => { if (target === 0) { distinct.push(list) return } for (let i = index; i < candidates.length; i++) { let diff = target - candidates[i]; if (diff >= 0) { //pass index as your current iteration dfs(candidates, diff, [...list, candidates[i]], i) } } } dfs(candidates, target) console.log(distinct); }; combinationSum([2, 3, 6, 7], 7);