# 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.

# 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”.

# LeetCode Subsets II

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: [1,2,2]
Output:
[
[2],
[1],
[1,2,2],
[2,2],
[1,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;
}
};

# LeetCode Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,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++) {
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;
}
};

# LeetCode Combinations

77. Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 … n.

Example:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,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;
}
};

class Solution {
public:
void dfs(vector<vector<int>> &ans, vector<int> &cand, int n, int k) {

if (cand.size() == k) {
ans.push_back(cand);
return;
}
if (n == 0)return;

cand.push_back(n);
dfs(ans, cand, n - 1, k);
cand.pop_back();

dfs(ans, cand, n - 1, k);
}
vector<vector<int>> combine(int n, int k) {
vector<int> cand;
vector<vector<int>> ans;
dfs(ans, cand, n, k);
return ans;
}
};

# 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 7 x 3 grid. How many possible unique paths are there?

Example 1:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right


Example 2:

Input: m = 7, n = 3
Output: 28


Constraints:

• 1 <= m, n <= 100
• It’s guaranteed that the answer will be less than or equal to 2 * 10 ^ 9.

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;
}
};

# LeetCode Combination Sum II

40. Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

Each number in candidates 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.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8,
A solution set is:
[
[1, 7],
[1, 2, 5],
[2, 6],
[1, 1, 6]
]


Example 2:

Input: candidates = [2,5,2,1,2], target = 5,
A solution set is:
[
[1,2,2],
[5]
]

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;
}
};

class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
if (target == 0) {
ans.push_back(cur);
return;
}
if (target < 0)return;
int i = idx;
while (i < candidates.size()) {
if (i > idx&&candidates[i] == candidates[i - 1]) {
++i;
continue;
}
target -= candidates[i];
cur.push_back(candidates[i]);
dfs(candidates, target, ans, cur, i + 1);
target += candidates[i];
cur.pop_back();
++i;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> cur;
sort(candidates.begin(), candidates.end());
dfs(candidates, target, ans, cur, 0);
return  ans;
}
};

# LeetCode Combination Sum

Given a set of candidate numbers (candidates(without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

The same repeated number may be chosen from candidates unlimited number of times.

Note:

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

Example 1:

Input: candidates = [2,3,6,7], target = 7,
A solution set is:
[
[7],
[2,2,3]
]


Example 2:

Input: candidates = [2,3,5], target = 8,
A solution set is:
[
[2,2,2,2],
[2,3,3],
[3,5]
]

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());
}
};

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;
}
};

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;
}
};

class Solution {
public:
void dfs(vector<int>& candidates, int target, vector<vector<int>>& ans, vector<int>& cur, int idx) {
if (target == 0) {
ans.push_back(cur);
return;
}
if (target < 0)return;
for (int i = idx; i < candidates.size(); ++i) {
target -= candidates[i];
cur.push_back(candidates[i]);
dfs(candidates, target, ans, cur, i);
cur.pop_back();
target += candidates[i];
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> cur;
dfs(candidates, target, ans, cur, 0);
return ans;
}
};