526互联

【DFS深度优先算法】全排列、组合总和

发布时间 2023-11-29 13:03:39作者: 钟离默

全排列

题目描述：给定一个没有重复数字的序列，返回其所有可能的全排列。

题目链接：46. 全排列

输入描述：
输入:[1,2,3]
输出描述：
输出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路：依次从前往后把所有数字，固定在第0个位置，此时再从前往后把剩余数字依次固定在第1个位置，如此递归，直到把倒数第二个数字固定，此时最后一个数字只剩一种可能，把整个序列放到结果中。

void DFS(std::vector<std::vector<int> >& retvec, std::vector<int>& vec, int fix)
{
	if (fix == vec.size() - 1)
	{
		retvec.emplace_back(vec);
		return;
	}


	for (int i = fix; i < vec.size(); ++i)
	{
		//每一位，都有N个可能
		std::swap(vec[i], vec[fix]);
		DFS(retvec, vec, fix + 1);
		std::swap(vec[i], vec[fix]);
	}
}

vector<vector<int>> permute(vector<int>& nums) {
	std::vector<std::vector<int> > retvec;
	DFS(retvec, nums, 0);
	return retvec;
}

全排列II

题目描述：给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

题目链接：47. 全排列 II

输入描述：
输入：nums = [1,1,2]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路：依次从前往后把所有数字，固定在第0个位置，如果这个数字已经在这个位置出现过，则跳过这个数字，此时再从前往后把剩余数字依次固定在第1个位置，如此递归，直到把倒数第二个数字固定，此时最后一个数字只剩一种可能，把整个序列放到结果中。

void DFS(std::vector<std::vector<int> >& retvec, std::vector<int>& vec, int fix)
{
	if (fix == vec.size() - 1)
	{
		retvec.emplace_back(vec);
		return;
	}

	std::set<int> fixset;//这个位置不能出现两次同一个数
	for (int i = fix; i < vec.size(); ++i)
	{
		if (fixset.count(vec[i]))
			continue;
		fixset.insert(vec[i]);
		//每一位，都有N个可能
		std::swap(vec[i], vec[fix]);
		DFS(retvec, vec, fix + 1);
		std::swap(vec[i], vec[fix]);
	}
}

vector<vector<int>> permuteUnique(vector<int>& nums) {
	std::vector<std::vector<int> > retvec;
	DFS(retvec, nums, 0);
	return retvec;
}

组合总和

题目描述：给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。

题目链接：39. 组合总和

示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：
输入: candidates = [2], target = 1
输出: []

思路：依次从前往后把所有数字放到当前的集合中并更新当前集合的和，此时又从前往后把所有数字（因为每个数字可以重复取，所以这里不是剩余数字）依次放入当前集合并更新当前集合的和，如此递归，直到当前集合的和等于target则将当前集合放入结果集合，如果集合的和大于target直接返回即可。

优化思路：这里会出现很多重复数据，比如candidates = [2,3], target = 5，会输出[[2,3],[3,2]]，这是因为在把3放入集合首位时，但是其实集合里有2、3和集合里有3、2的集合肯定是一样的集合。如果把源数据是进行升序排列，从前往后将数据放入当前集合中时，放2之后肯定会放3，那么当我放入3后，不用考虑放2，因为2比3小，之前放2的时候肯定放过3了，而且数据是升序的，如果把当前数据放入集合后，当前集合的和已经大于target了，由于后续所有的数字都不比当前数字小，就没必要继续放后面的数了，可以直接break。

void DFS(const std::vector<int>& candidates, std::vector<std::vector<int> >& retvec,
	std::vector<int>& curvec, int target, int fix)
{
	if (target == 0)
	{
		retvec.emplace_back(curvec);
		return;
	}

	for (int i = fix; i < candidates.size(); ++i)
	{
		if (target - candidates[i] < 0)
			break;
		curvec.emplace_back(candidates[i]);
		DFS(candidates, retvec, curvec, target - candidates[i], i);
		curvec.pop_back();
	}
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target)
{
	std::vector<int> curvec;
	std::vector<std::vector<int> > retvec;
	std::sort(candidates.begin(), candidates.end());
	DFS(candidates, retvec, curvec, target, 0);
	return retvec;
}