Solution Solution Leetcode  


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Adobe Airbnb Amazon себ Atlassian Блумберг ByteDance мехаранд Facebook Голдман Sachs Google LinkedIn Microsoft Oracle Snapchat хиёбони Uber VMware Озмоишгоҳҳои Walmart
алгоритмҳо тартиботи ҳарбӣ Бозгашт рамзгузорӣ мусоҳиба омодасозии мусоҳиба LeetCode LeetCodeSolutions

Мушкилоти Solution Combination Sum Leetcode моро таъмин менамояд асал ё рӯйхати бутунҳо ва ҳадаф. Ба мо гуфта мешавад, ки омезишҳоеро пайдо кунем, ки бо истифода аз ин ададҳо якчанд маротиба, ки ба ҳадафи додашуда илова мекунанд, сохта шаванд. Пас, ба таври расмӣ, мо метавонем бутунҳои додашударо якчанд маротиба истифода барем, то онҳо ба ҳадафи додашуда илова кунанд. Натиҷаи зарурӣ ин таркибҳоест, ки маблағи ба ҳадафи додашуда баробар мебошанд.

мисолSolution 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 натиҷаҳо ба ҳадафи додашуда ҷамъбаст карда мешаванд.

Равиш барои Solution Combination Leetcode  

Равиши мушкилотро ёфтан содда аст. Умуман, дар чунин мушкилот аз мо талаб карда мешавад, ки ақибнишиниро истифода барем. Зеро дар чунин саволҳо аз мо талаб карда мешавад, ки ҷустуҷӯи мукаммал анҷом диҳем ва посухашро пайдо кунем. Пас, аввал мо рӯйхати бутунҳои ба мо додашударо ҷобаҷо мекунем. Пас аз он, мо функсияи рекурсивӣ месозем, ки ба рӯйхати муваққатии ададҳои бутун илова кардани бутун ва нигоҳ доштани маблағи боқимондаро барои илова кардан ба ҳадафи додашуда идома медиҳад. Ҳамин тавр, дар дохили функсияи рекурсивӣ, мо ду ҳолати асосиро нигоҳ медорем. Аввалин ҳолати асосӣ санҷидани он аст, ки маблағи боқимондаи талабот манфӣ мешавад. Дар ин ҳолат, мо аз функсияи рекурсивӣ бармегардем. Ҳолати пойгоҳи дуюм шарти зарурии мо мебошад, агар маблағи боқимонда ба сифр баробар бошад. Агар маблағи боқимонда сифр бошад, ин маънои онро дорад, ки мо ба ҳадафи зарурӣ расидем. Дар он лаҳза, мо рӯйхати ҷории муваққатии бутунро ба массиви баромади массивҳо тела медиҳем.

ҳамчунин нигаред
Мушкилоти тағирёбии танга

рамз  

Коди C ++ барои Solution Combination Sum 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 барои Solution Combination Sum 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

Таҳлили мураккабӣ  

Мураккабии вақт

О (N ^ (M / T + 1)) ки дар он N шумораи номзадҳо, M хурдтарин номзад дар байни ҳамаи ададҳои додашуда ва T арзиши ҳадаф мебошад. Ҳамин тариқ, мураккабии вақт экспоненсиалӣ аст ва ин дар назар аст, зеро алгоритм бозгашти рекурсивӣ мебошад.

Мураккабии фазо

O (T / M), ки T арзиши ҳадаф аст ва M унсури минималӣ дар байни ҳамаи номзадҳои дигар.