კომბინირებული ჯამი Leetcode Solution  


Რთული ტური საშუალო
ხშირად ეკითხებიან Adobe Airbnb Amazon Apple Atlassian Bloomberg ByteDance eBay Facebook Goldman Sachs Google LinkedIn microsoft Oracle Snapchat Square Uber VMware Walmart Labs
ალგორითმები Array Backtracking კოდირება ინტერვიუ ინტერვიუს მოსამზადებელი LeetCode LeetCodeSolutions

პრობლემა კომბინირებული ჯამის Leetcode Solution გვაძლევს მასივი ან მთელი რიცხვების სია და სამიზნე. გვეუბნებიან, რომ იპოვოთ კომბინაციები, რომელთა გაკეთებაც შესაძლებელია ამ მთელი რიცხვების გამოყენებით, რამდენჯერმე შეემატება მოცემულ მიზანს. ასე რომ, უფრო ფორმალურად, შეგვიძლია გამოვიყენოთ მოცემული მთელი რიცხვები რამდენჯერმე ისე, რომ ისინი დაემატოს მოცემულ სამიზნეს. საჭირო გამომავალი არის კომბინაციები, რომელთა ჯამი მოცემული მიზნის ტოლია.

მაგალითიკომბინირებული ჯამი Leetcode Solution  

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. ჩვენ შეგვიძლია გადავამოწმოთ, რომ სამივე შედეგი ჯამდება მოცემულ სამიზნეზე.

მიდგომა კომბინირებული ჯამის 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

ჯავის კოდი კომბინირებული ჯამის 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 არის მინიმალური ელემენტი ყველა სხვა კანდიდატს შორის.