Прежде чем приступить к проблемам комбинаций, будет лучше, если мы немного обсудим это, что вы должны знать в первую очередь! Итак, давайте обсудим…
Что такое Комбинация?
Простым и понятным способом комбинация – это подмножество заданного набора, порядок которого не имеет значения. Давайте лучше разберемся в этом на примере примера – [1, 2, 3] все это комбинации – [[], [1], [2], [3], [1, 2], [1, 3], [2, 3] [1, 2, 3]]. Здесь вы можете заметить, что он не был написан таким образом – [1, 2] и [2, 1] или [1, 2, 3] и [2, 3, 1] и [3, 1, 2]. Потому что по определению мы знаем, что порядок не имеет значения. Означает здесь [1, 2] = [2, 1]. (любой, кого мы можем выбрать в качестве комбинации) ИЛИ [1, 2, 3] = [2, 1, 3] = [3, 1, 2]. Если два или более подмножеств имеют одинаковые элементы и их частоты также одинаковы, но порядок может отличаться или не отличаться, они считаются единым (одинаковым)!
Представление с использованием дерева
[]
/ \
/ \
[] [1]
/ \ / \
[] [2] [1] [1, 2]
/ \ / \ / \ / \
[] [3] [2] [2, 3] [1] [1, 3] [1, 2] [1, 2, 3]
Приведенные выше конечные узлы дают все комбинации данного массива [1, 2, 3]. Здесь интуиция заключается в том, чтобы выбрать и не выбирать элемент, таким образом, мы можем определить все возможные комбинации данного набора или массива. Теперь я расскажу о некоторых основных проблемах, связанных с комбинациями!
Проблема 1
Комбинации
Учитывая два целых числа n и k, верните все возможные комбинации из k чисел из диапазона [1, n].
Вы можете вернуть ответ в любом порядке. Пример 1:
Вход:, Выход: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] Пример 2:
Ввод:, Вывод: [[1]] Ограничения:
1 1
class Solution {
public List> combine(int n, int k) {
List> result = new ArrayList>();
combination(result, new ArrayList(), 1, n, k);
return result;
}
public static void combination(List> result, List 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);
}
}
}
Проблема 2
Сумма Комбинации
Учитывая массив различных целых чисел-кандидатов и целевую целочисленную цель, верните список всех уникальных комбинаций кандидатов, в которых выбранные числа суммируются с целевым значением. Вы можете возвращать комбинации в любом порядке.
Одно и то же число кандидатов может быть выбрано неограниченное количество раз. Две комбинации уникальны, если частота хотя бы одного из выбранных чисел отличается.
Гарантируется, что количество уникальных комбинаций, которые суммируются до целевого значения, составляет менее 150 комбинаций для данного ввода.
Пример 1:
Входные данные: кандидаты = [2,3,6,7], Вывод: [[2,2,3], [7]] Пояснение: 2 и 3 являются кандидатами, а 2 + 2 +. Обратите внимание, что 2 можно использовать несколько раз. 7 является кандидатом, и. Это единственные две комбинации. Пример 2:
Входные данные: кандидаты = [2,3,5], Выходной: [[2,2,2,2], [2,3,3], [3,5]] Пример 3:
Входные данные: кандидаты = [2], Вывод: [] Пример 4:
Входные данные: кандидаты = [1], Вывод: [[1]] Пример 5:
Входные данные: кандидаты = [1], Вывод: [[1,1]]
class Solution {
public List> combinationSum(int[] candidates, int target) {
// Arrays.sort(candidates);
List> res = new ArrayList();
find_comboSum(candidates, res, new ArrayList<>(), target, 0);
return res;
}
public static void find_comboSum(int[] arr, List> res, List 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);
}
}
}
Проблема 3
Сумма комбинации II
Учитывая набор номеров кандидатов (кандидатов) и целевой номер (target), найдите все уникальные комбинации в кандидатах, где номера кандидатов суммируются с целевым значением.
Каждое число в кандидатах может быть использовано только один раз в комбинации.
Примечание: Набор решений не должен содержать повторяющихся комбинаций.
Пример 1:
Входные данные: кандидаты = [10,1,2,7,6,1,5], Вывод: [ [1,1,6], [1,2,5], [1,7], [2,6] ] Пример 2:
Входные данные: кандидаты = [2,5,2,1,2], Вывод: [ [1,2,2], [5] ]
class Solution {
public List> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
List> res = new ArrayList<>();
find_combo(candidates, res, new ArrayList<>(), target, 0);
return res;
}
public static void find_combo(int[] arr, List> res, List 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);
}
}
}
Проблема 4
Сумма комбинации III
Найдите все допустимые комбинации из k чисел, сумма которых равна n, так что выполняются следующие условия:
Используются только цифры с 1 по 9. Каждый номер используется не более одного раза. Возвращает список всех возможных допустимых комбинаций. Список не должен содержать одну и ту же комбинацию дважды, и комбинации могут быть возвращены в любом порядке.
Пример 1:
Ввод:, Вывод: [[1,2,4]] Объяснение: 1 + 2 + Других допустимых комбинаций нет. Пример 2:
Вход:, Выход: [[1,2,6], [1,3,5], [2,3,4]] Объяснение: 1 + 2 + 1 + 3 + 2 + 3 + Других допустимых комбинаций не существует. Пример 3:
Ввод:, Вывод: [] Объяснение: Допустимых комбинаций не существует. [1,2,1] недопустимо, потому что 1 используется дважды. Пример 4:
Ввод:, Вывод: [] Объяснение: Допустимых комбинаций не существует. Пример 5:
Ввод:, Вывод: [[1,2,3,4,5,6,7,8,9]] Объяснение: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + Других допустимых комбинаций не существует.
Ограничения:
2 1
class Solution {
public List> combinationSum3(int k, int n) {
List> res = new ArrayList<>();
if(n < k)return res;
find_combo(res, new ArrayList<>(), k, 1, n);
return res;
}
public static void find_combo(List> res, List 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);
}
}
}
Спасибо за чтение… если у вас есть какие-либо сомнения или какие-либо предложения, не стесняйтесь комментировать это здесь, и самое главное, если вы обнаружите какую-либо ошибку, пожалуйста, дайте мне знать. Он будет мне очень благодарен ❤
Сучитра Следует
Оригинал: “https://dev.to/suchitra_13/combinations-problem-3f83”