Before start with the problems of combinations, It will be better if we discuss a bit about it that you should know first!
So, let's discuss…
What is Combination?
In a simple and easy way a combination is a subset of a given set in which order doesn't matter.
Let's understand it better with example
Example - [1, 2, 3]
it's all combinations are - [[], [1], [2], [3], [1, 2], [1, 3], [2, 3] [1, 2, 3]].
Here you might notice that it didn't write in this way - [1, 2] and [2, 1] or [1, 2, 3] and [2, 3, 1] and [3, 1, 2].
Because by the definition we know that order doesn't matter.
Means here [1, 2] = [2, 1]. (anyone we can pick as a combination)
OR [1, 2, 3] = [2, 1, 3] = [3, 1, 2].
If two or more subsets have the same elements and their frequencies are also the same, but the order may or may not be different they considered as a single one(same)!
Representation using tree
[]
/ \
/ \
[] [1]
/ \ / \
[] [2] [1] [1, 2]
/ \ / \ / \ / \
[] [3] [2] [2, 3] [1] [1, 3] [1, 2] [1, 2, 3]
The above leaf nodes give all combinations of the given array [1, 2, 3]. Here the intuition is pick and don't pick the element in this way we can determine all possible combinations of a given set or array.
Now, I will discuss some basic problem on combinations!
Problem 1
Combinations
Given two integers n and k, return all possible combinations of k numbers out of the range [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
class Solution {
public List<List<Integer>> combine(int n, int k) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
combination(result, new ArrayList<Integer>(), 1, n, k);
return result;
}
public static void combination(List<List<Integer>> result, List<Integer> list, int start, int n, int k){
if(k == 0){
result.add(new ArrayList<>(list));
return;
}
for(int i = start; i <= n - k + 1; i++){
list.add(i);
combination(result, list, i + 1, n, k - 1);
list.remove(list.size() - 1);
}
}
}
Problem 2
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]]
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList();
find_comboSum(candidates, res, new ArrayList<>(), target, 0);
return res;
}
public static void find_comboSum(int[] arr, List<List<Integer>> res, List<Integer> list, int target, int start){
if(target < 0)return;
if(target == 0){
res.add(new ArrayList(list));
return;
}
for(int i = start; i < arr.length; i++){
list.add(arr[i]);
find_comboSum(arr, res, list, target - arr[i], i);
list.remove(list.size() - 1);
}
}
}
Problem 3
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]
]
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List<List<Integer>> res = new ArrayList<>();
find_combo(candidates, res, new ArrayList<>(), target, 0);
return res;
}
public static void find_combo(int[] arr, List<List<Integer>> res, List<Integer> list, int target, int start){
if(target < 0)return;
if(target == 0){
res.add(new ArrayList(list));
return;
}
for(int i = start; i < arr.length; i++){
if(i > start && arr[i] == arr[i - 1])continue;
list.add(arr[i]);
find_combo(arr, res, list, target - arr[i], i + 1);
list.remove(list.size() - 1);
}
}
}
Problem 4
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
class Solution {
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> res = new ArrayList<>();
if(n < k)return res;
find_combo(res, new ArrayList<>(), k, 1, n);
return res;
}
public static void find_combo(List<List<Integer>> res, List<Integer> list, int k, int start, int n){
if(k == list.size() && n == 0){
res.add(new ArrayList<>(list));
return;
}
for(int i = start; i <= 9; i++){
list.add(i);
find_combo(res, list, k, i + 1, n - i);
list.remove(list.size() - 1);
}
}
}
Thanks for reading... if you have any doubts or any suggestions feel free to comment it here and most importantly if you find any bug please let me know. It will be very grateful to me ❤
Top comments (0)