Решение за комбиниран збир на леткод


Ниво на тешкотија Медиум
Често прашувано во Adobe Airbnb Амазон Јаболко Атласиан Блумберг ByteDance eBay Facebook Голдман Сакс Google Скопје Мајкрософт Oracle Snapchat Плоштад Uber VMware Лаборатории Walmart
Низа Враќање назад

Проблемот Комбинирано збирно решение Leetcode ни обезбедува an низа или список на цели броеви и цел. Ни е кажано да ги пронајдеме комбинациите што можат да се направат со користење на овие цели броеви, колку пати и се додаваат на дадената цел. Значи, поформално, можеме да ги користиме дадените цели броеви повеќе пати, такви што тие ќе додадат на дадената цел. Потребниот излез е комбинации што имаат збир еднаков на дадената цел.

примерРешение за комбиниран збир на леткод

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

Објаснување: Дадениот излез се сумира на дадената цел. Дури и ако се обидеме да излеземе со која било друга комбинација. Endе ги наредиме истите цели броеви по друг редослед. Но, редоследот не е важен само комбинациите.

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

Објаснување: Бидејќи можеме да го користиме истиот цел број кој било пати. Во излезот, користевме 2 повеќе пати во првиот излез. Слично на тоа, во вториот излез се повторува 2. Можеме да потврдиме дека сите 3 излези се сумираат на дадената цел.

Пристап за решение на комбиниран збир на код

Пристапот за проблемот е едноставен за наоѓање. Општо земено, во проблеми како што е ова, од нас се бара да користиме повратен удар. Бидејќи во такви прашања од нас се бара целосно пребарување и наоѓање на одговорот. Значи, прво, ние го сортираме списокот со цели броеви што ни е даден. После тоа, ние создаваме рекурзивна функција што продолжува да додава цел број на тековната привремена листа на цели броеви и да ја следи преостанатата сума потребна за да се додаде на дадената цел. Значи, во рамките на рекурзивната функција, чуваме два основни случаи. Првиот основен случај е да се провери дали преостанатата потребна сума оди негативно. Во тој случај, ќе се вратиме од рекурзивната функција. Вториот основен случај е нашиот потребен услов ако преостанатата сума е еднаква на нула. Ако преостанатата сума е нула, тоа значи дека ја достигнавме потребната цел. Во тој момент, ние ја туркаме тековната привремена листа на цели броеви во излезната низа на низи.

Код

C ++ код за решение за комбиниран збир на лек-код

#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

Јава код за Решение за комбиниран збир 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

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

Временска комплексност

О (Н ^ (М / Т + 1)) каде што N е бројот на кандидати, M е најмалиот кандидат меѓу сите дадени цели броеви, а T е целната вредност. Така, сложеноста на времето е експоненцијална и ова се очекува бидејќи алгоритмот е рекурзивен повратен удар.

Комплексноста на просторот

О (Т / М), каде Т е целната вредност и М е минималниот елемент меѓу сите други кандидати.