Λύση συνδυασμού συνολικού Leetcode  


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις πλίθα Airbnb αμαζόνα μήλο Atlassian Bloomberg ByteDance eBay Facebook Goldman Sachs Google LinkedIn Microsoft μαντείο Snapchat Τετράγωνα Uber VMware Εργαστήρια Walmart
αλγόριθμοι Παράταξη Οπισθοδρόμηση κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions

Το πρόβλημα 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  

Η προσέγγιση για το πρόβλημα είναι εύκολο να βρεθεί. Γενικά, σε προβλήματα όπως αυτό, απαιτείται να χρησιμοποιήσουμε το backtracking. Επειδή σε τέτοιες ερωτήσεις απαιτείται να κάνουμε μια πλήρη αναζήτηση και να βρούμε την απάντηση. Πρώτα λοιπόν, ταξινομούμε τη λίστα των ακεραίων που μας δίνεται. Στη συνέχεια, δημιουργούμε μια αναδρομική συνάρτηση που συνεχίζει να προσθέτει έναν ακέραιο στον τρέχοντα προσωρινό κατάλογο ακέραιων αριθμών και παρακολουθώντας το υπόλοιπο ποσό που απαιτείται για προσθήκη στον συγκεκριμένο στόχο. Έτσι, μέσα στην αναδρομική λειτουργία, διατηρούμε δύο βασικές περιπτώσεις. Η πρώτη βασική περίπτωση είναι να ελέγξετε εάν το υπόλοιπο ποσό που απαιτείται είναι αρνητικό. Σε αυτήν την περίπτωση, θα επιστρέψουμε από την αναδρομική συνάρτηση. Η δεύτερη βασική περίπτωση είναι η απαιτούμενη συνθήκη μας εάν το υπόλοιπο ποσό ισούται με μηδέν. Εάν το υπόλοιπο ποσό είναι μηδέν, αυτό σημαίνει ότι έχουμε επιτύχει τον απαιτούμενο στόχο μας. Σε αυτό το σημείο, ωθούμε την τρέχουσα προσωρινή λίστα ακεραίων στη σειρά εξόδου των συστοιχιών.

Βλέπε επίσης
Πρόβλημα αλλαγής νομισμάτων

Κώδικας  

Κωδικός C ++ για το Combination Sum 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 για το Combination Sum 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), όπου το Τ είναι η τιμή-στόχος και το Μ είναι το ελάχιστο στοιχείο μεταξύ όλων των άλλων υποψηφίων.

1