Комбинирано решение с Leetcode


Ниво на трудност M
Често задавани в Кирпич Airbnb Амазонка ябълка Atlassian Bloomberg ByteDance иБей Facebook Goldman Sachs Google LinkedIn Microsoft Оракул Snapchat Площад Uber VMware Walmart Labs
Array връщане назад

Проблемът Combination Sum Leetcode Solution ни предоставя масив или списък с цели числа и цел. Казват ни да намерим комбинациите, които могат да бъдат направени с помощта на тези цели числа, който и да е брой пъти, които се добавят към дадената цел. Така че по-формално можем да използваме дадените цели числа произволен брой пъти, така че те да се добавят към дадената цел. Необходимият резултат са комбинациите, чиято сума е равна на дадената цел.

ПримерКомбинирано решение с Leetcode

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

Обяснение: Даденият изход обобщава дадената цел. Дори да се опитаме да измислим някаква друга комбинация. В крайна сметка ще подредим едни и същи числа в различен ред. Но редът няма значение само комбинациите.

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

Обяснение: Тъй като можем да използваме едно и също число произволен брой пъти. В изхода използвахме 2 пъти по време на първия изход. По същия начин, във втория изход 2 се повтаря. Можем да проверим, че всичките 3 изхода се сумират за дадената цел.

Подход за комбинирано решение с Leetcode решение

Подходът за проблема е лесен за намиране. Като цяло при проблеми като този се изисква да използваме обратното проследяване. Защото при такива въпроси от нас се изисква да извършим цялостно търсене и да намерим отговора. Така че първо, ние сортираме списъка с цели числа, който ни е даден. След това създаваме рекурсивна функция, която продължава да добавя цяло число към текущия временен списък с цели числа и да следи оставащата сума, необходима за добавяне към дадената цел. Така че вътре в рекурсивната функция ние пазим два основни случая. Първият основен случай е да се провери дали оставащата необходима сума става отрицателна. В този случай ще се върнем от рекурсивната функция. Вторият базов случай е нашето задължително условие, ако останалата сума е равна на нула. Ако оставащата сума е нула, това означава, че сме достигнали желаната цел. В този момент натискаме текущия временен списък с цели числа в изходния масив от масиви.

код

C ++ код за решение с комбинация Leetcode

#include <bits/stdc++.h>
using namespace std;

void backtrack(vector<vector<int>> &output, vector<int> &current, vector<int> &candidates, int remain, int start){
    if(remain < 0)
        return;
    else if(remain == 0)output.push_back(current);
    else {
        for(int i=start;i<candidates.size();i++){
            current.push_back(candidates[i]);
            backtrack(output, current, candidates, remain - candidates[i], i);
            current.pop_back();
        }
    }
}

vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
    vector<vector<int>> output;
    vector<int> current;
    sort(candidates.begin(), candidates.end());
    backtrack(output, current, candidates, target, 0);
    return output;
}

int main(){
  vector<int> cand = {2, 3, 6, 7};
  vector<vector<int>> output = combinationSum(cand, 7)	;
  for(auto x: output){
    for(auto y: x)
      cout<<y<<" ";
    cout<<endl;
  }
}
2 2 3 
7

Java код за решение с комбинация Leetcode

import java.util.*;
import java.lang.*;
import java.io.*;

class Main
{
  public static List<List<Integer>> combinationSum(int[] nums, int target) {
      List<List<Integer>> list = new ArrayList<>();
      Arrays.sort(nums);
      backtrack(list, new ArrayList<>(), nums, target, 0);
      return list;
  }
  
  private static void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int remain, int start){
      if(remain < 0) return;
      else if(remain == 0) list.add(new ArrayList<>(tempList));
      else{ 
          for(int i = start; i < nums.length; i++){
              tempList.add(nums[i]);
              backtrack(list, tempList, nums, remain - nums[i], i); // not i + 1 because we can reuse same elements
              tempList.remove(tempList.size() - 1);
          }
      }
  }

  public static void main (String[] args) throws java.lang.Exception
  {
    int[] nums = {2, 3, 6, 7};
    List<List<Integer>> output = combinationSum(nums, 7);
    for(List<Integer> x: output){
      for(Integer y: x)
        System.out.print(y+" ");
      System.out.println();
    }
  }
}
2 2 3
7

Анализ на сложността

Сложност във времето

O (N ^ (M / T + 1)) където N е броят на кандидатите, M е най-малкият кандидат сред всички дадени цели числа, а T е целевата стойност. По този начин сложността на времето е експоненциална и това се очаква, тъй като алгоритъмът е рекурсивно обратно проследяване.

Сложност на пространството

O (T / M), където T е целевата стойност, а M е минималният елемент сред всички останали кандидати.