{"id":973,"date":"2025-12-15T17:11:04","date_gmt":"2025-12-15T09:11:04","guid":{"rendered":"https:\/\/www.guanhaobo.cn\/?p=973"},"modified":"2025-12-15T17:11:04","modified_gmt":"2025-12-15T09:11:04","slug":"leetcode-39-%e7%bb%84%e5%90%88%e6%80%bb%e5%92%8c","status":"publish","type":"post","link":"https:\/\/www.guanhaobo.cn\/?p=973","title":{"rendered":"LeetCode 39 – \u7ec4\u5408\u603b\u548c"},"content":{"rendered":"

\u9898\u76ee\u63cf\u8ff0<\/h1>\n

\u7ed9\u4f60\u4e00\u4e2a \u65e0\u91cd\u590d\u5143\u7d20 \u7684\u6574\u6570\u6570\u7ec4 candidates \u548c\u4e00\u4e2a\u76ee\u6807\u6574\u6570 target \uff0c\u627e\u51fa candidates \u4e2d\u53ef\u4ee5\u4f7f\u6570\u5b57\u548c\u4e3a\u76ee\u6807\u6570 target \u7684 \u6240\u6709 \u4e0d\u540c\u7ec4\u5408 \uff0c\u5e76\u4ee5\u5217\u8868\u5f62\u5f0f\u8fd4\u56de\u3002\u4f60\u53ef\u4ee5\u6309 \u4efb\u610f\u987a\u5e8f \u8fd4\u56de\u8fd9\u4e9b\u7ec4\u5408\u3002
\ncandidates \u4e2d\u7684 \u540c\u4e00\u4e2a \u6570\u5b57\u53ef\u4ee5 \u65e0\u9650\u5236\u91cd\u590d\u88ab\u9009\u53d6 \u3002\u5982\u679c\u81f3\u5c11\u4e00\u4e2a\u6570\u5b57\u7684\u88ab\u9009\u6570\u91cf\u4e0d\u540c\uff0c\u5219\u4e24\u79cd\u7ec4\u5408\u662f\u4e0d\u540c\u7684\u3002
\n\u5bf9\u4e8e\u7ed9\u5b9a\u7684\u8f93\u5165\uff0c\u4fdd\u8bc1\u548c\u4e3a target \u7684\u4e0d\u540c\u7ec4\u5408\u6570\u5c11\u4e8e 150 \u4e2a\u3002<\/p>\n

\u793a\u4f8b\uff1a
\n\u8f93\u5165\uff1acandidates = [2,3,6,7], target = 7
\n\u8f93\u51fa\uff1a[[2,2,3],[7]]<\/p>\n

\u9898\u76ee\u5206\u6790<\/h1>\n

\u7ec4\u5408\uff0c\u672c\u8d28\u662f\u5355\u5411\u7684\u6392\u5217\u3002
\n\u5728 DFS \u65f6\u589e\u52a0\u53c2\u6570 index \u8868\u793a\u5f53\u524d\u6570\u5b57\u7684\u4f4d\u7f6e\uff0c\u4fdd\u8bc1\u540e\u7eed\u53ea\u5411\u53f3\uff08>=index\uff09\u4e0d\u5411\u5de6\u5373\u53ef\u3002<\/p>\n

Java<\/h1>\n
private List<List<Integer>> ans = new ArrayList<>();\nprivate List<Integer> list = new ArrayList<>();\nprivate int sum = 0;\n\npublic List<List<Integer>> combinationSum(int[] candidates, int target) {\n    dfs(candidates, target, 0);\n    return ans;\n}\n\nprivate void dfs(int[] candidates, int target, int index) {\n    if (sum > target) {\n        return;\n    }\n    if (sum == target) {\n        ans.add(new ArrayList<>(list));\n        return;\n    }\n    for (int i = index; i < candidates.length; i++) {\n        list.add(candidates[i]);\n        sum += candidates[i];\n        dfs(candidates, target, i);\n        sum -= candidates[i];\n        list.remove(list.size() - 1);\n    }\n}\n<\/code><\/pre>\n
Kotlin<\/h1>\n
private val ans = ArrayList<List<Int>>()\nprivate val list = ArrayList<Int>()\nprivate var sum = 0\n\nfun combinationSum(candidates: IntArray, target: Int): List<List<Int>> {\n    dfs(candidates, target, 0)\n    return ans\n}\n\nprivate fun dfs(candidates: IntArray, target: Int, index: Int) {\n    if (sum > target) {\n        return\n    }\n    if (sum == target) {\n        ans.add(ArrayList(list))\n        return\n    }\n    for (i in index until candidates.size) {\n        list.add(candidates[i])\n        sum += candidates[i]\n        dfs(candidates, target, i)\n        list.removeLast()\n        sum -= candidates[i]\n    }\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0 \u7ed9\u4f60\u4e00\u4e2a \u65e0\u91cd\u590d\u5143\u7d20 \u7684\u6574\u6570\u6570\u7ec4 candidates \u548c\u4e00\u4e2a\u76ee\u6807\u6574\u6570 target \uff0c\u627e\u51fa can […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[11,20,90,91],"class_list":["post-973","post","type-post","status-publish","format-standard","hentry","category-algo","tag-dfs","tag-leetcode","tag-90","tag-91"],"_links":{"self":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/973","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=973"}],"version-history":[{"count":1,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/973\/revisions"}],"predecessor-version":[{"id":974,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=\/wp\/v2\/posts\/973\/revisions\/974"}],"wp:attachment":[{"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=973"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=973"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.guanhaobo.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=973"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}