combination sum solution

robinyoon-dev · robinyoon-dev · commit 95cc89bf3918 · 2026-03-18T10:47:46.000+09:00
diff --git a/combination-sum/robinyoon-dev.js b/combination-sum/robinyoon-dev.js
@@ -0,0 +1,36 @@
+/**
+ * @param {number[]} candidates
+ * @param {number} target
+ * @return {number[][]}
+ */
+var combinationSum = function (candidates, target) {
+
+    const result = [];
+
+    function dfs(remainTarget, currentArray, currentIndex) {
+
+        if (remainTarget < 0) {
+            return;
+        }
+
+        if (remainTarget == 0) {
+            result.push([...currentArray]);
+            return;
+        }
+
+        // 백트래킹 탐색
+        for (let i = currentIndex; i < candidates.length; i++) {
+            currentArray.push(candidates[i]);
+
+            dfs(remainTarget - candidates[i], currentArray, i);
+
+            currentArray.pop();
+        }
+
+    }
+
+    dfs(target, [], 0);
+
+    return result;
+
+};
