קאָמבינאַציע סאַם לעעטקאָדע סאַלושאַן  


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַדאָובי אַירבנב אַמאַזאָן עפּל אַטלאַססיאַן בלומבערג ביטעדאַנסע עבייַ facebook גאָלדמאַן סאַקס גוגל לינקעדין מייקראָסאָפֿט אָראַקל Snapchat קוואַדראַט ובער וומוואַרע וואַלמאַרט לאַבס
אַלגערידאַמז מענגע Backtracking קאָדירונג אינטערוויו interviewprep LeetCode LeetCodeSolutions

די פּראָבלעם קאָמבינאַציע סאַם לעעטקאָדע סאַלושאַן גיט אונדז אַן מענגע אָדער רשימה פון ינטאַדזשערז און אַ ציל. מיר זייַנען געזאָגט צו געפֿינען די קאַמבאַניישאַנז וואָס קענען זיין געמאכט מיט די גאַנץ נומערן קיין נומער פון צייט צו די ציל. אַזוי מער פאָרמאַללי, מיר קענען נוצן די געגעבן ינטאַדזשערז קיין נומער פון צייט אַזאַ ווי זיי לייגן צו די געגעבן ציל. די פארלאנגט רעזולטאַט איז די קאַמבאַניישאַנז אַז די סומע איז גלייַך צו די געגעבן ציל.

בייַשפּילקאָמבינאַציע סאַם לעעטקאָדע סאַלושאַן  

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 אַוטפּוץ סומע אַרויף צו די געגעבן ציל.

צוגאַנג פֿאַר קאָמבינאַציע סומע לעעטקאָדע סאַלושאַן  

דער צוגאַנג פֿאַר דעם פּראָבלעם איז פּשוט צו געפֿינען. אין אַלגעמיין, אין אַזאַ פּראָבלעמס, מיר דאַרפֿן צו נוצן באַקקטראַקקינג. ווייַל אין אַזאַ פֿראגן מיר דאַרפֿן צו דורכפירן אַ גאַנץ זוכן און געפֿינען דעם ענטפער. ערשטער, מיר סאָרט די רשימה פון ינטאַדזשערז וואָס זענען געגעבן צו אונדז. דערנאָך מיר מאַכן אַ רעקורסיווע פונקציע וואָס האלט צו לייגן אַ ינטאַדזשער צו די קראַנט צייַטווייַליק רשימה פון ינטאַדזשערז און האַלטן די רוען סומע וואָס איז פארלאנגט צו לייגן אַרויף צו די געגעבן ציל. אַזוי אין די רעקורסיווע פונקציע, מיר האַלטן צוויי באַזע קאַסעס. דער ערשטער באַזע איז צו קאָנטראָלירן צי די רוען סומע איז נעגאַטיוו. אין דעם פאַל, מיר וועלן צוריקקומען פון די רעקורסיווע פונקציע. די רגע באַזע איז אונדזער פארלאנגט צושטאַנד אויב די רוען סומע איז גלייך צו נול. אויב די רוען סומע איז נול, דאָס מיינט אַז מיר האָבן ריטשט אונדזער פארלאנגט ציל. אין דעם פונט, מיר שטופּן די קראַנט צייַטווייַליק רשימה פון ינטאַדזשערז אין די רעזולטאַט מענגע פון ​​ערייז.

זע אויך
מאַטבייע ענדערונג פּראָבלעם

קאָדעקס  

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

דזשאַוואַ קאָד פֿאַר קאָמבינאַטיאָן סאַם לעעטקאָדע סאַלושאַן

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 איז די ציל ווערט. אזוי די צייט קאַמפּלעקסיטי איז עקספּאָונענשאַל און דאָס איז געריכט ווייַל די אַלגערידאַם איז רעקורסיווע באַקטראַקקינג.

ספעיס קאַמפּלעקסיטי

אָ (ה / ב), וווּ T איז די ציל ווערט און M איז די מינימאַל עלעמענט צווישן אַלע אנדערע קאַנדאַדייץ.