Камбінаванае рашэнне Leetcode


Узровень складанасці серада
Часта пытаюцца ў Саман Airbnb амазонка яблык Atlassian Bloomberg ByteDance eBay facebook Goldman Sachs Google LinkedIn Microsoft Аракул Snapchat Плошча Uber VMware Лабараторыі Walmart
масіў Фанаграмы

Праблема 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 Solution

#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 Solution

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), дзе Т - мэтавае значэнне, а М - мінімальны элемент сярод усіх іншых кандыдатаў.