{"type":"doc","content":[{"type":"extension","attrs":{"layout":"default","extensionType":"com.atlassian.confluence.macro.core","extensionKey":"toc","parameters":{"macroParams":{"style":{"value":"none"}},"macroMetadata":{"macroId":{"value":"3d7b13bb-b375-47a1-b8ef-7e7aff1aa774"},"schemaVersion":{"value":"1"},"title":"Table of Contents"}},"localId":"aef8a7e6-6b8d-470e-8459-5574d4fafa3f"}},{"type":"heading","attrs":{"level":1},"content":[{"text":"排列 / 组合 / 子集","type":"text"}]},{"type":"paragraph","content":[{"text":"形式一、元素无重不可复选，即 ","type":"text","marks":[{"type":"strong"}]},{"text":"nums","type":"text","marks":[{"type":"code"}]},{"text":" 中的元素都是唯一的，每个元素最多只能被使用一次，这也是最基本的形式","type":"text","marks":[{"type":"strong"}]},{"text":"。","type":"text"}]},{"type":"paragraph","content":[{"text":"以组合为例，如果输入 ","type":"text"},{"text":"nums = [2,3,6,7]","type":"text","marks":[{"type":"code"}]},{"text":"，和为 7 的组合应该只有 ","type":"text"},{"text":"[7]","type":"text","marks":[{"type":"code"}]},{"text":"。","type":"text"}]},{"type":"paragraph","content":[{"text":"形式二、元素可重不可复选，即 ","type":"text","marks":[{"type":"strong"}]},{"text":"nums","type":"text","marks":[{"type":"code"}]},{"text":" 中的元素可以存在重复，每个元素最多只能被使用一次","type":"text","marks":[{"type":"strong"}]},{"text":"。","type":"text"}]},{"type":"paragraph","content":[{"text":"以组合为例，如果输入 ","type":"text"},{"text":"nums = [2,5,2,1,2]","type":"text","marks":[{"type":"code"}]},{"text":"，和为 7 的组合应该有两种 ","type":"text"},{"text":"[2,2,2,1]","type":"text","marks":[{"type":"code"}]},{"text":" 和 ","type":"text"},{"text":"[5,2]","type":"text","marks":[{"type":"code"}]},{"text":"。","type":"text"}]},{"type":"paragraph","content":[{"text":"形式三、元素无重可复选，即 ","type":"text","marks":[{"type":"strong"}]},{"text":"nums","type":"text","marks":[{"type":"code"}]},{"text":" 中的元素都是唯一的，每个元素可以被使用若干次","type":"text","marks":[{"type":"strong"}]},{"text":"。","type":"text"}]},{"type":"paragraph","content":[{"text":"以组合为例，如果输入 ","type":"text"},{"text":"nums = [2,3,6,7]","type":"text","marks":[{"type":"code"}]},{"text":"，和为 7 的组合应该有两种 ","type":"text"},{"text":"[2,2,3]","type":"text","marks":[{"type":"code"}]},{"text":" 和 ","type":"text"},{"text":"[7]","type":"text","marks":[{"type":"code"}]},{"text":"。","type":"text"}]},{"type":"paragraph","content":[{"text":"当然，也可以说有第四种形式，即元素可重可复选。但既然元素可复选，那又何必存在重复元素呢？元素去重之后就等同于形式三，所以这种情况不用考虑。","type":"text"}]},{"type":"paragraph","content":[{"text":"上面用组合问题举的例子，但排列、组合、子集问题都可以有这三种基本形式，所以共有 9 种变化。","type":"text"}]},{"type":"heading","attrs":{"level":2},"content":[{"text":"元素无重不可复选","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[子集] LC 78. Subsets 子集","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/subsets/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func subsets(nums []int) (result [][]int) {\n var prev []int\n \n var backtrack func(start int)\n backtrack = func(start int) {\n result = append(result, append([]int(nil), prev...))\n \n for i := start; i < len(nums); i++ {\n prev = append(prev, nums[i])\n backtrack(i + 1)\n prev = prev[:len(prev)-1]\n }\n }\n \n backtrack(0)\n \n return\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[组合] LC 77. Combinations 组合","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/combinations/description/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"组合和子集是一样的：大小为 ","type":"text","marks":[{"type":"strong"}]},{"text":"k","type":"text","marks":[{"type":"code"}]},{"text":" 的组合就是大小为 ","type":"text","marks":[{"type":"strong"}]},{"text":"k","type":"text","marks":[{"type":"code"}]},{"text":" 的子集","type":"text","marks":[{"type":"strong"}]},{"text":"。","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func combine(n int, k int) (result [][]int) {\n var prev []int\n \n var backtrack func(start int)\n backtrack = func(start int) {\n if len(prev) == k {\n result = append(result, append([]int(nil), prev...))\n return\n }\n \n for i := start; i <= n; i++ {\n prev = append(prev, i)\n backtrack(i+1)\n prev = prev[:len(prev)-1]\n }\n }\n backtrack(1)\n \n return\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[排列] LC 46. Permutations 全排列","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/permutations/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func permute(nums []int) (result [][]int) {\n used := make(map[int]bool, 6)\n var prev []int\n \n var backtrack func()\n backtrack = func() {\n if len(prev) == len(nums) {\n result = append(result, append([]int(nil), prev...))\n return\n }\n \n for i := 0; i < len(nums); i++ {\n num := nums[i]\n \n if used[num] { \n continue \n }\n \n prev = append(prev, num)\n used[num] = true\n \n backtrack()\n \n prev = prev[:len(prev)-1]\n delete(used, num)\n }\n }\n backtrack()\n \n return\n}","type":"text"}]},{"type":"heading","attrs":{"level":4},"content":[{"text":"扩展：只有 k 个元素的排列（不是全排列）","type":"text"}]},{"type":"paragraph","content":[{"text":"改下 ","type":"text"},{"text":"backtrack","type":"text","marks":[{"type":"code"}]},{"text":" 函数的 base case，仅收集第 ","type":"text"},{"text":"k","type":"text","marks":[{"type":"code"}]},{"text":" 层的节点值即可","type":"text"}]},{"type":"codeBlock","content":[{"text":"func backtrack(nums []int, k int) {\n // base case，到达第 k 层，收集节点的值\n if len(track) == k {\n // 第 k 层节点的值就是大小为 k 的排列\n res = append(res, append([]int(nil), track...))\n return\n }\n\n // 回溯算法标准框架\n for i := 0; i < len(nums); i++ {\n // ...\n backtrack(nums, k)\n // ...\n }\n}","type":"text"}]},{"type":"heading","attrs":{"level":2},"content":[{"text":"元素可重不可复选","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[子集] LC 90. Subsets II 子集 II","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/subsets-ii"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"和元素不可重的区别：需要先进行排序，让相同的元素靠在一起，如果发现 ","type":"text","marks":[{"type":"strong"}]},{"text":"nums[i] == nums[i-1]","type":"text","marks":[{"type":"code"}]},{"text":"，则跳过","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","content":[{"text":"func subsetsWithDup(nums []int) (result [][]int) {\n sort.Ints(nums)\n \n var prev []int\n \n var backtrack func(start int)\n backtrack = func(start int) {\n result = append(result, append([]int(nil), prev...))\n \n for i := start; i < len(nums); i++ {\n if i > start && nums[i] == nums[i-1] {\n continue\n }\n \n num := nums[i]\n \n prev = append(prev, num)\n backtrack(i+1)\n prev = prev[:len(prev)-1]\n }\n }\n backtrack(0)\n \n return result\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[组合] LC 40. Combination sum II 组合总和 II","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/combination-sum-ii/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func combinationSum2(candidates []int, target int) (result [][]int) {\n sort.Ints(candidates)\n \n var prev []int\n var prevSum int\n \n var backtrack func(start int)\n backtrack = func(start int) {\n if prevSum == target {\n result = append(result, append([]int(nil), prev...))\n }\n if prevSum >= target {\n return\n }\n \n for i := start; i < len(candidates); i++ {\n if i > start && candidates[i] == candidates[i-1] {\n continue\n }\n \n prev = append(prev, candidates[i])\n prevSum += candidates[i]\n \n backtrack(i+1)\n \n prev = prev[:len(prev)-1]\n prevSum -= candidates[i]\n }\n }\n \n backtrack(0)\n return\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[排列] LC 47. 全排列 II","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/permutations-ii/description/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"标准全排列算法之所以出现重复，是因为把相同元素形成的排列序列视为不同的序列，但实际上它们应该是相同的；而如果固定相同元素形成的序列顺序，当然就避免了重复","type":"text","marks":[{"type":"strong"}]},{"text":"。","type":"text"}]},{"type":"paragraph","content":[{"text":"那么反映到代码上，你注意看这个剪枝逻辑：","type":"text"}]},{"type":"codeBlock","content":[{"text":"// 新添加的剪枝逻辑，固定相同的元素在排列中的相对位置\nif (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {\n // 如果前面的相邻相等元素没有用过，则跳过\n continue;\n}\n// 选择 nums[i]","type":"text"}]},{"type":"paragraph","content":[{"text":"当出现重复元素时，比如输入 ","type":"text","marks":[{"type":"strong"}]},{"text":"nums = [1,2,2',2'']","type":"text","marks":[{"type":"code"}]},{"text":"，","type":"text","marks":[{"type":"strong"}]},{"text":"2'","type":"text","marks":[{"type":"code"}]},{"text":" 只有在 ","type":"text","marks":[{"type":"strong"}]},{"text":"2","type":"text","marks":[{"type":"code"}]},{"text":" 已经被使用的情况下才会被选择，同理，","type":"text","marks":[{"type":"strong"}]},{"text":"2''","type":"text","marks":[{"type":"code"}]},{"text":" 只有在 ","type":"text","marks":[{"type":"strong"}]},{"text":"2'","type":"text","marks":[{"type":"code"}]},{"text":" 已经被使用的情况下才会被选择，这就保证了相同元素在排列中的相对位置保证固定","type":"text","marks":[{"type":"strong"}]},{"text":"。","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func permuteUnique(nums []int) (result [][]int) {\n used := make([]bool, 9)\n prev := make([]int, 0, 8)\n \n sort.Ints(nums)\n \n var backtrack func()\n backtrack = func() {\n if len(prev) == len(nums) {\n result = append(result, append([]int(nil), prev...))\n return\n }\n \n for i := 0; i < len(nums); i++ {\n num := nums[i]\n \n if i > 0 && nums[i] == nums[i-1] && !used[i-1] {\n continue\n }\n \n if used[i] {\n continue\n }\n \n prev = append(prev, num)\n used[i] = true\n \n backtrack()\n \n prev = prev[:len(prev)-1]\n used[i] = false\n }\n }\n backtrack()\n \n return\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"另一种剪枝思路","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func permuteUnique(nums []int) (result [][]int) {\n used := make([]bool, 9)\n prev := make([]int, 0, 8)\n \n sort.Ints(nums)\n \n var backtrack func()\n backtrack = func() {\n if len(prev) == len(nums) {\n result = append(result, append([]int(nil), prev...))\n return\n }\n \n prevNum := 1024\n for i := 0; i < len(nums); i++ {\n num := nums[i]\n \n if used[i] || num == prevNum {\n continue\n }\n \n prev = append(prev, num)\n used[i] = true\n prevNum = num\n \n backtrack()\n \n prev = prev[:len(prev)-1]\n used[i] = false\n }\n }\n backtrack()\n \n return\n}","type":"text"}]},{"type":"heading","attrs":{"level":2},"content":[{"text":"元素无重可复选","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[组合/子集] LC 39. Combination Sum 组合总和","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/combination-sum/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func combinationSum(candidates []int, target int) (result [][]int) {\n var prev []int\n var prevSum int\n \n var backtrack func(start int)\n backtrack = func(start int) {\n if prevSum == target {\n result = append(result, append([]int(nil), prev...))\n }\n if prevSum >= target {\n return\n }\n \n for i := start; i < len(candidates); i++ {\n prev = append(prev, candidates[i])\n prevSum += candidates[i]\n \n backtrack(i)\n \n prev = prev[:len(prev)-1]\n prevSum -= candidates[i]\n }\n }\n backtrack(0)\n \n return\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"[排列]","type":"text"}]},{"type":"paragraph","content":[{"text":"标准的全排列算法利用 ","type":"text","marks":[{"type":"strong"}]},{"text":"used","type":"text","marks":[{"type":"code"}]},{"text":" 数组进行剪枝，避免重复使用同一个元素。如果允许重复使用元素的话，直接放飞自我，去除所有 ","type":"text","marks":[{"type":"strong"}]},{"text":"used","type":"text","marks":[{"type":"code"}]},{"text":" 数组的剪枝逻辑就行了","type":"text","marks":[{"type":"strong"}]},{"text":"。","type":"text"}]},{"type":"codeBlock","content":[{"text":"func permuteRepeat(nums []int) [][]int {\n var res [][]int\n var track []int\n \n backtrack(nums, &res, track)\n \n return res\n}\n\n// 回溯算法核心函数\nfunc backtrack(nums []int, res *[][]int, track []int) {\n // base case，到达叶子节点\n if len(track) == len(nums) {\n // 收集叶子节点上的值\n tmp := make([]int, len(track))\n copy(tmp, track)\n *res = append(*res, tmp)\n return\n }\n\n // 回溯算法标准框架\n for i := 0; i < len(nums); i++ {\n // 做选择\n track = append(track, nums[i])\n // 进入下一层回溯树\n backtrack(nums, res, track)\n // 取消选择\n track = track[:len(track)-1]\n }\n}","type":"text"}]}],"version":1}

Browser not supported