Tag Archives: 组合

LeetCode Increasing Subsequences

LeetCode Increasing Subsequences
Given an integer array, your task is to find all the different possible increasing subsequences of the given array, and the length of an increasing subsequence should be at least 2 .
Example:

Input: [4, 6, 7, 7]
Output: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

Note:

  1. The length of the given array will not exceed 15.
  2. The range of integer in the given array is [-100,100].
  3. The given array may contain duplicates, and two equal integers should also be considered as a special case of increasing sequence.

给定一个数组,求出改数组的所有递增子序列。注意两点,一是递增,二是子序列。
因为是求子序列,所以没必要对数组排序!
使用DFS,尝试将每个数加入cand,然后从下一个数开始,如果比cand的最后一个数大,则递归DFS。比较简单的思路。
需要注意的点是,结果不能有重复数组,所以需要满足第19、6行的条件,并且用set去重。
第19行条件:比如样例[4,4,6,7,7,8,9,10],第一个4为起点的DFS的结果已经包含第二个4为起点的DFS结果,所以需要第19行。
第6行条件:比如样例[4,4,6,7,7,8,9,10],从6开始DFS时,遇到第一个7和遇到第二个7后续DFS的结果都是一样的,所以需要第6行。
set去重:还会遇到这样的样例比如样例[4,6,7,4,8,9,10],第一个4DFS的结果包含了第二个4DFS的结果,但是这两个4不相邻,所以不能被第19行的条件防止重复,只能用set去重了。
代码如下:

class Solution {
private:
	void dfs(set<vector<int>>& ans, vector<int>& nums, vector<int>& cand, int start){
		if(cand.size() >= 2)ans.insert(cand);
		for(int i = start + 1; i < nums.size(); ++i){
			if(i == start + 1 || nums[i] != nums[i - 1]){
				if(nums[i] >= cand[cand.size() - 1]){
					cand.push_back(nums[i]);
					dfs(ans, nums, cand, i);
					cand.pop_back();
				}
			}
		}
	}
public:
    vector<vector<int>> findSubsequences(vector<int>& nums) {
    	set<vector<int>> ans;
    	for(int i = 0; i < nums.size(); ++i){
    		if(i == 0 || nums[i] != nums[i-1]){
    			vector<int> cand = {nums[i]};
    			dfs(ans, nums, cand, i);
    		}
    	}
    	return vector<vector<int>>(ans.begin(), ans.end());
    }
};

本代码提交AC,用时269MS。

LeetCode Binary Watch

LeetCode Binary Watch
A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).
Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads "3:25".
Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
Example:

Input: n = 1
Return: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]

Note:

  • The order of output does not matter.
  • The hour must not contain a leading zero, for example "01:00" is not valid, it should be "1:00".
  • The minute must be consist of two digits and may contain a leading zero, for example "10:2" is not valid, it should be "10:02".

程序员有一个二进制的手表,如图所示,上面4个灯表示小时,下面6个灯表示分钟。现在告诉你手表上亮着n盏灯,问共有多少种时间的可能,要求输出所有可能的时间。
我觉得这应该算中等题,稍微有一点麻烦。
首先我们要把亮着的n盏灯分到小时和分钟上,比如小时亮x盏灯,分钟亮y盏灯,x+y=n。对于小时,长度为4bit,要把亮着的x盏灯填入这4bit中,共有C_4^x种填法,可以用递归的思路实现。对于分钟,长度为6bit,要把亮着的y盏灯填入这6bit中,共有C_6^y种填法,也可以用递归的思路实现。
所以我们可以统一小时和分钟的递归算法,具体看代码comb函数。假设初始的灯的状态为cur,我们就是要在cur的[s,t) bit之间填入ones个1bit,对于小时,长度为4bit,所以传入cur=0, s=0, t=4;对于分钟,长度为6bit,所以传入cur=0, s=0, t=6。注意每次递归调用的时候,s都要更新,否则生成的组合结果会有重复。
生成了小时和分钟的组合之后,我们再把小时和分钟字符串组合起来,这个就简单了,不再赘述。完整代码如下:

class Solution {
public:
	// cur为传入的二进制串,comb要把ones个1填入[s,t)中
	void comb(vector<int>& res, int cur, int s, int t, int ones) {
		if (ones == 0)res.push_back(cur);
		else {
			for (int i = s; i < t; ++i) {
				if ((cur&(1 << i)) == 0) {
					comb(res, cur | (1 << i), i + 1, t, ones - 1); // 递归把ones-1个1填入[i+1,t)中
				}
			}
		}
	}
	vector<string> readBinaryWatch(int num) {
		vector<string> ans;
		for (int hour = 0; hour <= 3; ++hour) {
			if (hour > num)break;
			vector<int> hours;
			comb(hours, 0, 0, 4, hour);
			vector<int> minutes;
			comb(minutes, 0, 0, 6, num - hour);
			for (int i = 0; i < hours.size(); ++i) {
				if (hours[i] > 11)continue;
				string tmp_h = to_string(hours[i]);
				for (int j = 0; j < minutes.size(); ++j) {
					if (minutes[j] > 59)continue;
					string tmp_m = to_string(minutes[j]);
					if (tmp_m.size() < 2)tmp_m = "0" + tmp_m;
					ans.push_back(tmp_h + ":" + tmp_m);
				}
			}
		}
		return ans;
	}
};

本代码提交AC,用时0MS。

LeetCode Subsets II

LeetCode Subsets II
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

求一个“集合”的所有子集,和LeetCode Subsets的区别是本题中,原始“集合”可能包含重复元素,和LeetCode Permutations II很类似。
只需在LeetCode Subsets的基础上增加一个判断,如果在递归的时候发现某个元素和上一个元素相同,则不添加,即不再以该元素独立新开一个递归下去。
举个例子,样例中的{1,2,2},第一次递归的时候,我们会尝试分别以1,2和2递归,但是发现第二个2和前一个元素2相同,所以我们不再以第二个2开一个新的递归下去。但是我们在以第一个2开递归的时候,发现后面有一个2时,并不阻止这个2加到原有的集合中去,也就是子集{2,2}还是会产生的。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& cand, vector<int>& nums, int step) {
		ans.push_back(cand);
		for (int i = step; i < nums.size(); i++) {
			if (i != step && nums[i] == nums[i - 1]) { // caution: i!=step
				continue;
			}
			cand.push_back(nums[i]);
			work(ans, cand, nums, i + 1);
			cand.pop_back();
		}
	}
	vector<vector<int>> subsetsWithDup(vector<int>& nums) {
		vector<vector<int>> ans;
		vector<int> cand;
		sort(nums.begin(), nums.end()); // 先对原数组排序
		work(ans, cand, nums, 0);
		return ans;
	}
};

注意判断的条件是i!=step,而不是i!=0,因为如果是i!=0,则{2,2}这种情况也会被禁止掉。
本代码提交AC,用时6MS。

LeetCode Subsets

LeetCode Subsets
Given a set of distinct integers, nums, return all possible subsets.
Note: The solution set must not contain duplicate subsets.
For example,
If nums = [1,2,3], a solution is:

[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

求一个集合的所有子集,高中就知道所有子集个数为2^n个,包括空集和它本身。
算法思路和LeetCode Combinations几乎一样,只不过成功条件不再是candidate中有k个数了,而是每添加一个元素都算成功一个。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& cand, vector<int>& nums, int step) {
		ans.push_back(cand);
		for (int i = step; i < nums.size(); i++) {
			cand.push_back(nums[i]);
			work(ans, cand, nums, i + 1);
			cand.pop_back();
		}
	}
	vector<vector<int>> subsets(vector<int>& nums) {
		vector<vector<int>> ans;
		vector<int> cand;
		work(ans, cand, nums, 0);
		return ans;
	}
};

本代码提交AC,用时3MS。

LeetCode Combinations

LeetCode Combinations
Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

求1~n的所有k组合数,和求排列数有点类似。当然也是递归的思路,每个数都有取和不取两种情况,分别递归。唯一需要注意的是递归遍历的时候不走回头路,这样才不会重复。比如求1,2,3,4的两数组合,第一个取1,第二个可以取2,3,4;当第一个取2时,就不再回过头来测试1了,因为之前测试1时,已经产生了{1,2}这个组合,现在测试2时,只需要往前测试3,4了。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidate, int step, int& n, int& k) {
		if (candidate.size() == k) {
			ans.push_back(candidate);
		}
		else {
			for (int i = step; i <= n; i++) { // 从第step步开始
				candidate.push_back(i);
				work(ans, candidate, i + 1, n, k); // 下一步从i+1步开始
				candidate.pop_back();
			}
		}
	}
	vector<vector<int>> combine(int n, int k) {
		vector<vector<int>> ans;
		vector<int> cand;
		work(ans, cand, 1, n, k);
		return ans;
	}
};

本代码提交AC,用时113MS。

LeetCode Unique Paths

LeetCode Unique Paths
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.


问从左上角走到右下角一共有多少种方案,每次只能往右或者下走。很简单的题,高中学过排列组合的都知道。
假设右下和左上的坐标之差为(x,y),则从左上走到右下一共需要走x+y步,可以分为x步往右走,y步往下走。每一步都可以选择往右或者往下走,所以总的方案数为C_{x+y}^x==C_{x+y}^y,用x,y中的较小者来算就可以了,计算方法就是高中数学老师教的啦:-)
完整代码如下

class Solution {
public:
	int uniquePaths(int m, int n) {
		int x = m - 1, y = n - 1;
		int z = x + y, u = x < y ? x : y;
		double ans = 1.0;
		for (int i = 1; i <= u; i++) {
			ans *= z;
			ans /= i;
			z--;
		}
		return ans;
	}
};

本代码提交AC,用时0MS。

LeetCode Combination Sum II

LeetCode Combination Sum II
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8,
A solution set is:

[
  [1, 7],
  [1, 2, 5],
  [2, 6],
  [1, 1, 6]
]

这题和之前的LeetCode Combination Sum很类似,但是要求同一个数字不能重复选,不过candidates里面可能会有重复的数字。所以策略就是在一个for循环里面判断数字是否重复,注意不能在递归里面判断所选数字是否重复,因为递归的时候是可以选相同数字的,比如样例的[1,1,6]。同时递归的时候传入当前下标的下一个下标。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = idx; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				if (i != idx && candidates[i] == candidates[i - 1])continue; // i != idx
				sol.push_back(candidates[i]);
				work(ans, candidates, i + 1, sol, target - candidates[i]); // i + 1
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, 0, sol, target);
		return ans;
	}
};

本代码提交AC,用时10MS。

LeetCode Combination Sum

LeetCode Combination Sum
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:

  • All numbers (including target) will be positive integers.
  • The solution set must not contain duplicate combinations.

For example, given candidate set [2, 3, 6, 7] and target 7,
A solution set is:

[
  [7],
  [2, 2, 3]
]

本题要从一个集合中取出一些数,使得和为某个特定的数target,输出所有的这种组合。注意不能有重复的组合,比如[2,2,3]和[3,2,2]算是重复的。
这是很常见的组合问题,使用递归的思路求解。比如样例,要求和为7,则每个加数必须小于等于7,所以依次尝试2,3,6,7,如果是2,则还差7-2=5,所以递归的在[2,3,6,7]里面找和为5的组合。如此递归,直到差为0。但是这样有一个问题,比如你这一次尝试的是2,则可能得到[2,2,3]的组合,下一次尝试3,则可能得到[3,2,2]的组合,但是这两个组合是相同的。我一开始的想法是对组合排序,然后用set去重。代码如下:

class Solution {
public:
	void work(set<vector<int>>& ans, vector<int>& candidates, vector<int>& sol, int target) {
		if (target == 0) {
			vector<int> tmp = sol;
			sort(tmp.begin(), tmp.end());
			ans.insert(tmp);
		}
		else {
			for (int i = 0; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				sol.push_back(candidates[i]);
				work(ans, candidates, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		set<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, sol, target);
		return vector<vector<int>>(ans.begin(), ans.end());
	}
};

本代码提交AC,但是用时145MS,只击败了4.5%的人,所以肯定还有更优的方案。
上述方案的一个费时的地方就是要对每个组合排序,然后用set去重,如果能省掉这个环节,速度会快很多。
网上查看题解之后,恍然大悟,每次只选不小于上一次选过的数,这样得到的组合就不会有重复,不需要排序,也不需要set去重。比如上面的例子,在选到3时,差7-3=4,此时再从[2,3,6,7]里面选时,只选大于等于3的数,也就是3,6,7,不再考虑2了。但是6,7都大于4,不行;3的话,剩余4-3=1也无解。所以搜3的时候,就不会得到[3,2,2]的结果,也就无需去重。
完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = 0; i < candidates.size(); i++) {
				if (candidates[i] > target || (sol.size() > 0 && candidates[i] < sol[sol.size() - 1]))continue;
				sol.push_back(candidates[i]);
				work(ans, candidates, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, sol, target);
		return ans;
	}
};

本代码提交AC,用时20MS,速度快了好多。
后来我发现这个版本的代码还可以优化,因为candidates已经排好序了,如果这次取了i号元素,下一次只要取i及以后的元素即可,所以在递归的时候多传入一个下标值,也能提速。完整代码如下:

class Solution {
public:
	void work(vector<vector<int>>& ans, vector<int>& candidates, int idx, vector<int>& sol, int target) {
		if (target == 0) {
			ans.push_back(sol);
		}
		else {
			for (int i = idx; i < candidates.size(); i++) {
				if (candidates[i] > target)break;
				sol.push_back(candidates[i]);
				work(ans, candidates, i, sol, target - candidates[i]);
				sol.pop_back();
			}
		}
	}
	vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
		vector<vector<int>> ans;
		vector<int> sol;
		sort(candidates.begin(), candidates.end());
		work(ans, candidates, 0, sol, target);
		return ans;
	}
};

本代码提交AC,用时16MS。