- 例题
- 1. 全排列
- 2. 全排列II
- 377. 组合总和 Ⅳ">3. lc 377. 组合总和 Ⅳ
- 518. 零钱兑换 II">4. lc 518. 零钱兑换 II
- 零钱兑换">5. lc 322 零钱兑换
- 6. 组合
- 7. 组合总和II
例题
1. 全排列
描述 
思路
对每一个位置，使用或不使用，进行回溯搜索。使用used数组来标记。
代码
Python代码：
class Solution:def permute(self, nums: List[int]) -> List[List[int]]:res = []length = len(nums)used = [False for i in nums]path = []def dfs(nums, depth, path, length, used):if depth == length:res.append(path.copy())returnfor i in range(len(nums)):if used[i]:continuepath.append(nums[i])used[i] = Truedfs(nums, depth+1, path, length, used)path.pop()used[i] = Falsedfs(nums,0,path,length,used)return res
Java代码：
class Solution {
public List<List<Integer>> permute(int[] nums) {
int len = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
Deque<Integer> path = new ArrayDeque<Integer>();
boolean[] used = new boolean[len];
dfs(nums, len, 0, path, used, res);
return res;
}
private void dfs(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) {
if (depth == len) {
res.add(new ArrayList<>(path));
}
for (int i=0; i <len; i++) {
if (used[i]) {
continue;
}
path.addLast(nums[i]);
used[i] = true;
dfs(nums, len, depth+1, path, used, res);
path.removeLast();
used[i] = false;
}
}
}
2. 全排列II
描述 
思路
此题同上题的区别在于，存在重复元素。
有两种办法：
- 在加入结果集时候进行去重；
- 搜索的时候进行剪枝
如果要比较两个列表是否一样，一个很显然的办法是分别排序，然后逐个比对。既然要排序，我们可以在搜索之前就对候选数组排序，一旦发现这一支搜索下去可能搜索到重复的元素就停止搜索，这样结果集中不会包含重复元素。
上一次的 1 刚刚被撤销，正是因为刚被撤销，下面的搜索中还会使用到，因此会产生重复，剪掉的就应该是这样的分支。
核心：
- 数组先排序
增加以下代码
if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continueif (i > 0 && nums[i] == nums[i-1] && !used[i-1]) { continue; }代码
Python代码：class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: def dfs(path, depth, used, i): if depth == len(nums): res.append(path.copy()) for i in range(len(nums)): if used[i]: continue if i > 0 and nums[i] == nums[i-1] and not used[i-1]: continue used[i] = True path.append(nums[i]) dfs(path, depth+1, used, i) used[i] = False path.pop() nums.sort() res = [] path = [] used = [False] * len(nums) dfs(path, 0, used, 0) return resJava代码：
class Solution { public List<List<Integer>> permuteUnique(int[] nums) { int len = nums.length; List<List<Integer>> res = new ArrayList<>(); if (len == 0) { return res; } Deque<Integer> path = new ArrayDeque<Integer>(); boolean[] used = new boolean[len]; Arrays.sort(nums); dfs(nums, len, 0, path, used, res); return res; } private void dfs(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> res) { if (depth == len) { res.add(new ArrayList<>(path)); } for (int i=0; i <len; i++) { if (used[i]) { continue; } if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) { continue; } path.addLast(nums[i]); used[i] = true; dfs(nums, len, depth+1, path, used, res); path.removeLast(); used[i] = false; } } }3. lc 377. 组合总和 Ⅳ
描述
思路输入数组的每个元素可以使用多次，这一点和「完全背包」问题有点像；
- 顺序不同的序列被视作不同的组合，这一点和所有的「背包问题」都不同，与 518. 零钱兑换 II 问题不同的地方就在这一点。
常规思路大概有「回溯搜索」、「动态规划」；不需要记录搜索路径的，可以用动态规划来做。
代码
Java代码：
public class Solution {
/**
* 这里状态定义就是题目要求的，并不难，状态转移方程要动点脑子，也不难：
* 状态转移方程：dp[i]= dp[i - nums[0]] + dp[i - nums[1]] + dp[i - nums[2]] + ... （当 [] 里面的数 >= 0）
* 特别注意：dp[0] = 1，表示，如果那个硬币的面值刚刚好等于需要凑出的价值，这个就成为 1 种组合方案
* 再举一个具体的例子：nums=[1, 3, 4], target=7;
* dp[7] = dp[6] + dp[4] + dp[3]
* 即：7 的组合数可以由三部分组成，1 和 dp[6]，3 和 dp[4], 4 和dp[3];
*
* @param nums
* @param target
* @return
*/
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
// 这个值被其它状态参考，设置为 1 是合理的
dp[0] = 1;
for (int i = 1; i <= target; i++) {
for (int num : nums) {
if (num <= i) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
}
Python代码：
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp = [0] * (target + 1)
dp[0] = 1
for i in range(1, target+1):
for num in nums:
if num <= i:
dp[i] += dp[i - num]
return dp[target]
4. lc 518. 零钱兑换 II
描述 
思路
这道题是典型的“完全背包问题”。“完全背包问题”的特点是：背包里的物品可以无限次选取。
本题特殊的地方在于：从背包里选取的物品必须刚刚好装满需要考虑的容量，而不是小于等于就好，注意这点细微的区别。
完全背包问题是基于 0-1 背包问题的扩展。它们的不同之处在于：
0-1 背包问题：当前考虑的物品用或者不用；
完全背包问题：当前考虑的物品用或者不用，如果用，用几个。
代码
Python代码：
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
return dp[amount]
这里是遍历每一个硬币值，然后遍历钱数。
Java完全背包：
class Solution {
public int change(int amount, int[] coins) {
int n = coins.length;
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] = dp[j] + dp[j - coins[i]];
}
}
return dp[amount];
}
}
5. lc 322 零钱兑换
思路
- 动态规划
- 每个金额，遍历硬币数，取最小的值，注意当前金币是否能达到该金额
- 遍历每个硬币，计算能组成的amout的最小值
- 两种方式初始化不太一样
代码
Java代码1：
public class Solution {
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
}
Java代码2：
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
Arrays.fill(dp, -1);
dp[0] = 0;
for (int i = 1; i < amount + 1; i++) {
for (int coin : coins) {
if (i - coin >= 0 && dp[i - coin] != -1) {
if (dp[i] == -1 || dp[i] > dp[i - coin] + 1) {
dp[i] = dp[i-coin] + 1;
}
}
}
}
return dp[amount];
}
}
Python代码1：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for x in range(coin, amount + 1):
dp[x] = min(dp[x], dp[x - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Python代码2：
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
n = amount
dp = [-1 for i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
for coin in coins:
if i - coin >= 0 and dp[i-coin] != -1:
if dp[i] == -1 or dp[i] > dp[i-coin] + 1:
dp[i] = dp[i-coin] + 1
return dp[n]
6. 组合
思路
- 回溯
代码
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(begin, path):
if len(path) == k:
res.append(path.copy())
for i in range(begin, n+1):
path.append(i)
backtrack(i+1, path)
path.pop()
res = []
path = []
backtrack(1, path)
return res
7. 组合总和II
public class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
List<List<Integer>> res = new ArrayList<>();
if (len == 0) {
return res;
}
// 关键步骤
Arrays.sort(candidates);
Deque<Integer> path = new ArrayDeque<>(len);
dfs(candidates, len, 0, target, path, res);
return res;
}
/**
* @param candidates 候选数组
* @param len 冗余变量
* @param begin 从候选数组的 begin 位置开始搜索
* @param target 表示剩余，这个值一开始等于 target，基于题目中说明的"所有数字（包括目标数）都是正整数"这个条件
* @param path 从根结点到叶子结点的路径
* @param res
*/
private void dfs(int[] candidates, int len, int begin, int target, Deque<Integer> path, List<List<Integer>> res) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = begin; i < len; i++) {
// 大剪枝：减去 candidates[i] 小于 0，减去后面的 candidates[i + 1]、candidates[i + 2] 肯定也小于 0，因此用 break
if (target - candidates[i] < 0) {
break;
}
// 小剪枝：同一层相同数值的结点，从第 2 个开始，候选数更少，结果一定发生重复，因此跳过，用 continue
if (i > begin && candidates[i] == candidates[i - 1]) {
continue;
}
path.addLast(candidates[i]);
// 调试语句 ①
// System.out.println("递归之前 => " + path + "，剩余 = " + (target - candidates[i]));
// 因为元素不可以重复使用，这里递归传递下去的是 i + 1 而不是 i
dfs(candidates, len, i + 1, target - candidates[i], path, res);
path.removeLast();
// 调试语句 ②
// System.out.println("递归之后 => " + path + "，剩余 = " + (target - candidates[i]));
}
}
public static void main(String[] args) {
int[] candidates = new int[]{10, 1, 2, 7, 6, 1, 5};
int target = 8;
Solution solution = new Solution();
List<List<Integer>> res = solution.combinationSum2(candidates, target);
System.out.println("输出 => " + res);
}
}
若有收获，就点个赞吧
0 人点赞
