leetcode 377 - Combination Sum IV

https://leetcode.com/problems/combination-sum-iv/

Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target.

Example:

nums = [1, 2, 3]
target = 4

The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

Note that different sequences are counted as different combinations.

Therefore the output is 7.

Follow up:
What if negative numbers are allowed in the given array?
How does it change the problem?
What limitation we need to add to the question to allow negative numbers?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<unsigned long> dp(target + 1);

dp[0] = 1;

for (int t = 1; t <= target; t++) {
dp[t] = 0;

for (int num : nums) {
if (t - num < 0)
continue;

dp[t] += dp[t - num];
}
}

return dp[target];
}
};

leetcode 216 - Combination Sum III

Find all valid combinations of k numbers that sum up to n such that the following conditions are true:

Only numbers 1 through 9 are used.
Each number is used at most once.
Return a list of all possible valid combinations. The list must not contain the same combination twice, and the combinations may be returned in any order.

Example 1:

Input: k = 3, n = 7
Output: [[1,2,4]]
Explanation:
1 + 2 + 4 = 7
There are no other valid combinations.
Example 2:

Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
There are no other valid combinations.
Example 3:

Input: k = 4, n = 1
Output: []
Explanation: There are no valid combinations. [1,2,1] is not valid because 1 is used twice.
Example 4:

Input: k = 3, n = 2
Output: []
Explanation: There are no valid combinations.
Example 5:

Input: k = 9, n = 45
Output: [[1,2,3,4,5,6,7,8,9]]
Explanation:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45
There are no other valid combinations.

Constraints:

2 <= k <= 9
1 <= n <= 60

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<vector<int>> all_result;

vector<vector<int>> combinationSum3(int k, int n) {
vector<int> result;

combinationSum3(k, n, 1, result);
return all_result;
}

void combinationSum3(int k, int n, int i, vector<int> &result) {
if (n <= 0 || i > 9 || result.size() == k) {
if (n == 0 && result.size() == k)
all_result.push_back(result);
return;
}

for (int j = i; j <= 9; j++) {
result.push_back(j);
combinationSum3(k, n - j, j + 1, result);
result.pop_back();
}
}
};

leetcode 40 - Combination Sum II

https://leetcode.com/problems/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 sum to target.

Each number in candidates may only be used once in the combination.

Note: The solution set must not contain duplicate combinations.

Example 1:

Input: candidates = [10,1,2,7,6,1,5], target = 8
Output:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
Example 2:

Input: candidates = [2,5,2,1,2], target = 5
Output:
[
[1,2,2],
[5]
]

Constraints:

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public:
vector<vector<int>> all_result;

vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> result;

sort(candidates.begin(), candidates.end());
combinationSum2(candidates, target, 0, result);
return all_result;
}

void combinationSum2(vector<int>& candidates, int target, int i, vector<int> &result) {
int size = candidates.size();

if (target <= 0 || i == size) {
if (target == 0)
all_result.push_back(result);
return;
}

for (int j = i; j < size; j++) {
if (j > i && candidates[j] == candidates[j - 1])
continue;

result.push_back(candidates[j]);
combinationSum2(candidates, target - candidates[j], j + 1, result);
result.pop_back();
}
}
};

leetcode 39 - Combination Sum

https://leetcode.com/problems/combination-sum/

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order.

The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different.

It is guaranteed that the number of unique combinations that sum up to target is less than 150 combinations for the given input.

Example 1:

Input: candidates = [2,3,6,7], target = 7
Output: [[2,2,3],[7]]
Explanation:
2 and 3 are candidates, and 2 + 2 + 3 = 7. Note that 2 can be used multiple times.
7 is a candidate, and 7 = 7.
These are the only two combinations.
Example 2:

Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Example 3:

Input: candidates = [2], target = 1
Output: []
Example 4:

Input: candidates = [1], target = 1
Output: [[1]]
Example 5:

Input: candidates = [1], target = 2
Output: [[1,1]]

Constraints:

1 <= candidates.length <= 30
1 <= candidates[i] <= 200
All elements of candidates are distinct.
1 <= target <= 500

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
vector<vector<int>> all_result;

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> result;

combinationSum(candidates, target, 0, result);
return all_result;
}

void combinationSum(vector<int>& candidates, int target, int i, vector<int> &result) {
if (target <= 0 || i == (int)candidates.size()) {
if (target == 0)
all_result.push_back(result);
return;
}

result.push_back(candidates[i]);
combinationSum(candidates, target - candidates[i], i, result);
result.pop_back();

combinationSum(candidates, target, i + 1, result);
}
};

leetcode 77 - Combinations

https://leetcode.com/problems/combinations/

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

You may return the answer in any order.

Example 1:

Input: n = 4, k = 2
Output:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]
Example 2:

Input: n = 1, k = 1
Output: [[1]]

Constraints:

1 <= n <= 20
1 <= k <= n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
vector<vector<int>> all_result;

vector<vector<int>> combine(int n, int k) {
vector<int> result;

combine(n, k, 1, result);
return all_result;
}

void combine(int n, int k, int i, vector<int> &result) {
if (result.size() == k) {
all_result.push_back(result);
return;
}

if (i > n)
return;

for (int j = i; j <= n; j++) {
result.push_back(j);
combine(n, k, j + 1, result);
result.pop_back();
}
}
};

leetcode 60 - Permutation Sequence

https://leetcode.com/problems/permutation-sequence/
https://leetcode.com/problems/permutation-sequence/discuss/22544/Easy-understand-Most-concise-C%2B%2B-solution-minimal-memory-required

The set [1, 2, 3, …, n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

“123”
“132”
“213”
“231”
“312”
“321”
Given n and k, return the kth permutation sequence.

Example 1:

Input: n = 3, k = 3
Output: “213”
Example 2:

Input: n = 4, k = 9
Output: “2314”
Example 3:

Input: n = 3, k = 1
Output: “123”

Constraints:

1 <= n <= 9
1 <= k <= n!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
string getPermutation(int n, int k) {
string s(n, '0');
int p = 1;

for (int i = 1; i <= n; i++) {
s[i-1] += i;
p = p * i;
}

//important: make "k/p" get correct idx
k--;

for (int i = 0; k >= 0 && i < n; i++) {
p = p / (n - i);
int idx = k / p;
k -= idx * p;

idx += i;
char c = s[idx];
for (int j = idx; j > i; j--)
s[j] = s[j - 1];

s[i] = c;
}

return s;
}
};

leetcode 31 - Next Permutation

https://leetcode.com/problems/next-permutation/

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]
Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]
Example 4:

Input: nums = [1]
Output: [1]

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 100

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if (next(nums) == false)
reverse(nums.begin(), nums.end());
}

bool next(vector<int> &nums) {
int size = nums.size();

for (int i = size - 1; i >= 0; i--) {
if (i < size - 1 && nums[i] < nums[i + 1]) {
for (int j = size - 1; j >= i + 1; j--) {
if (nums[j] > nums[i]) {
swap(nums[j], nums[i]);
reverse(nums.begin() + i + 1, nums.end());
return true;
}
}
}
}

return false;
}
};

leetcode 47 - Permutations II

https://leetcode.com/problems/permutations-ii/

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Example 1:

Input: nums = [1,1,2]
Output:
[[1,1,2],
[1,2,1],
[2,1,1]]
Example 2:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Constraints:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> result;

permute(nums, nums.size(), 0, result);
return result;
}

void permute(vector<int> &nums, int size, int i, vector<vector<int>> &result) {
if (i == size) {
result.push_back(nums);
return;
}

unordered_set<int> used;

for (int k = i; k < size; k++) {
if (used.count(nums[k]))
continue;

used.insert(nums[k]);

swap(nums[k], nums[i]);
permute(nums, size, i+1, result);
swap(nums[k], nums[i]);
}
}
};

class Solution {
public:
vector<vector<int>> all_result;

vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(), nums.end());

int size = nums.size();
vector<bool> used(size, false);

vector<int> result(size);

permute(nums, result, used, size, 0);

return all_result;
}

void permute(vector<int>& nums, vector<int> &result, vector<bool> &used, int size, int i) {
if (i == size) {
all_result.push_back(result);
return;
}

int prev_idx = -1;

for (int k = 0; k < size; k++) {
if (!used[k]) {
if (prev_idx != -1 && nums[k] == nums[prev_idx])
continue;

prev_idx = k;
used[k] = true;
result[i] = nums[k];
permute(nums, result, used, size, i + 1);
used[k] = false;
}
}
}
};

leetcode 46 - Permutations

https://leetcode.com/problems/permutations/

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Example 1:

Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
Example 2:

Input: nums = [0,1]
Output: [[0,1],[1,0]]
Example 3:

Input: nums = [1]
Output: [[1]]

Constraints:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
All the integers of nums are unique.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int>> result;

permute(nums, nums.size(), 0, result);
return result;
}

void permute(vector<int> &nums, int size, int i, vector<vector<int>> &result) {
if (i == size) {
result.push_back(nums);
return;
}

for (int k = i; k < size; k++) {
swap(nums[k], nums[i]);
permute(nums, size, i+1, result);
swap(nums[k], nums[i]);
}
}
};

leetcode 319 - Bulb Switcher

https://leetcode.com/problems/bulb-switcher/
https://leetcode.com/problems/bulb-switcher/discuss/77104/Math-solution..

There are n bulbs that are initially off. You first turn on all the bulbs, then you turn off every second bulb.

On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the ith round, you toggle every i bulb. For the nth round, you only toggle the last bulb.

Return the number of bulbs that are on after n rounds.

Example 1:

Input: n = 3
Output: 1
Explanation: At first, the three bulbs are [off, off, off].
After the first round, the three bulbs are [on, on, on].
After the second round, the three bulbs are [on, off, on].
After the third round, the three bulbs are [on, off, off].
So you should return 1 because there is only one bulb is on.
Example 2:

Input: n = 0
Output: 0
Example 3:

Input: n = 1
Output: 1

Constraints:

0 <= n <= 10^9

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
int bulbSwitch(int n) {
int on = 0;

for (int i = 1; i <= n; i++) {
int flip = get_divisors(i);

on += (flip % 2);
}

return on;
}

int get_divisors(int n) {
if (n == 1) return 1;
if (n <= 3) return 2;

int q = sqrt(n);

int total = 0;

for (int i = 1; i <= q; i++) {
if (n % i == 0)
total += 2;
}

total -= (q * q == n);

return total;
}
};

class Solution {
public:
int bulbSwitch(int n) {
return sqrt(n);
}
};