ಸಂಯೋಜನೆಯ ಮೊತ್ತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ airbnb ಅಮೆಜಾನ್ ಆಪಲ್ Atlassian ಬ್ಲೂಮ್ಬರ್ಗ್ ಬೈಟ್ ಡೇನ್ಸ್ ಇಬೇ ಫೇಸ್ಬುಕ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗೂಗಲ್ ಸಂದೇಶ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಒರಾಕಲ್ Snapchat ಸ್ಕ್ವೇರ್ ಉಬರ್ ವರೆ ವಾಲ್ಮಾರ್ಟ್ ಲ್ಯಾಬ್ಸ್
ಅರೇ ಬ್ಯಾಕ್‌ಟ್ರಾಕಿಂಗ್

ಕಾಂಬಿನೇಶನ್ ಸಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರವು ನಮಗೆ ಒಂದು ಒದಗಿಸುತ್ತದೆ ಸರಣಿ ಅಥವಾ ಪೂರ್ಣಾಂಕಗಳ ಪಟ್ಟಿ ಮತ್ತು ಗುರಿ. ಕೊಟ್ಟಿರುವ ಗುರಿಯನ್ನು ಸೇರಿಸುವ ಯಾವುದೇ ಬಾರಿ ಈ ಪೂರ್ಣಾಂಕಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಮಾಡಬಹುದಾದ ಸಂಯೋಜನೆಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ನಮಗೆ ತಿಳಿಸಲಾಗಿದೆ. ಆದ್ದರಿಂದ ಹೆಚ್ಚು ly ಪಚಾರಿಕವಾಗಿ, ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕಗಳನ್ನು ಅವರು ನಿರ್ದಿಷ್ಟ ಗುರಿಗೆ ಸೇರಿಸುವ ಯಾವುದೇ ಬಾರಿ ಬಳಸಬಹುದು. ಅಗತ್ಯವಿರುವ output ಟ್‌ಪುಟ್ ನಿರ್ದಿಷ್ಟ ಸಂಯೋಜನೆಯ ಮೊತ್ತವನ್ನು ಹೊಂದಿರುವ ಸಂಯೋಜನೆಗಳಾಗಿವೆ.

ಉದಾಹರಣೆಸಂಯೋಜನೆಯ ಮೊತ್ತ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರ

candidates = [2,3,6,7], target = 7
[[2,2,3],[7]]

ವಿವರಣೆ: ಕೊಟ್ಟಿರುವ output ಟ್‌ಪುಟ್ ನಿರ್ದಿಷ್ಟ ಗುರಿಯವರೆಗೆ ಮೊತ್ತವನ್ನು ನೀಡುತ್ತದೆ. ನಾವು ಬೇರೆ ಯಾವುದೇ ಸಂಯೋಜನೆಯೊಂದಿಗೆ ಬರಲು ಪ್ರಯತ್ನಿಸಿದರೂ ಸಹ. ನಾವು ಒಂದೇ ಪೂರ್ಣಾಂಕಗಳನ್ನು ಬೇರೆ ಕ್ರಮದಲ್ಲಿ ಜೋಡಿಸುವುದನ್ನು ಕೊನೆಗೊಳಿಸುತ್ತೇವೆ. ಆದರೆ ಸಂಯೋಜನೆಯು ಮಾಡುವಂತೆ ಆದೇಶವು ಅಪ್ರಸ್ತುತವಾಗುತ್ತದೆ.

candidates = [2,3,5], target = 8
[[2,2,2,2],[2,3,3],[3,5]]

ವಿವರಣೆ: ನಾವು ಒಂದೇ ಪೂರ್ಣಾಂಕವನ್ನು ಎಷ್ಟು ಬಾರಿ ಬಳಸಬಹುದು. Output ಟ್ಪುಟ್ನಲ್ಲಿ, ನಾವು ಮೊದಲ .ಟ್ಪುಟ್ನಲ್ಲಿ 2 ಅನೇಕ ಬಾರಿ ಬಳಸಿದ್ದೇವೆ. ಅಂತೆಯೇ, ಎರಡನೇ output ಟ್ಪುಟ್ನಲ್ಲಿ 2 ಪುನರಾವರ್ತನೆಯಾಗುತ್ತದೆ. ಎಲ್ಲಾ 3 uts ಟ್‌ಪುಟ್‌ಗಳು ಕೊಟ್ಟಿರುವ ಗುರಿಯ ಮೊತ್ತವನ್ನು ಹೊಂದಿದೆಯೆ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬಹುದು.

ಕಾಂಬಿನೇಶನ್ ಸಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಅನುಸಂಧಾನ

ಸಮಸ್ಯೆಯ ವಿಧಾನವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ಸರಳವಾಗಿದೆ. ಸಾಮಾನ್ಯವಾಗಿ, ಈ ರೀತಿಯ ಸಮಸ್ಯೆಗಳಲ್ಲಿ, ನಾವು ಬ್ಯಾಕ್‌ಟ್ರಾಕಿಂಗ್ ಅನ್ನು ಬಳಸಬೇಕಾಗುತ್ತದೆ. ಏಕೆಂದರೆ ಅಂತಹ ಪ್ರಶ್ನೆಗಳಲ್ಲಿ ನಾವು ಸಂಪೂರ್ಣ ಹುಡುಕಾಟ ನಡೆಸಬೇಕು ಮತ್ತು ಉತ್ತರವನ್ನು ಕಂಡುಹಿಡಿಯಬೇಕು. ಆದ್ದರಿಂದ ಮೊದಲು, ನಮಗೆ ನೀಡಲಾದ ಪೂರ್ಣಾಂಕಗಳ ಪಟ್ಟಿಯನ್ನು ನಾವು ವಿಂಗಡಿಸುತ್ತೇವೆ. ನಂತರ, ನಾವು ಪುನರಾವರ್ತಿತ ಕಾರ್ಯವನ್ನು ರಚಿಸುತ್ತೇವೆ ಅದು ಪ್ರಸ್ತುತ ತಾತ್ಕಾಲಿಕ ಪೂರ್ಣಾಂಕಗಳ ಪಟ್ಟಿಗೆ ಒಂದು ಪೂರ್ಣಾಂಕವನ್ನು ಸೇರಿಸುತ್ತಲೇ ಇರುತ್ತದೆ ಮತ್ತು ಕೊಟ್ಟಿರುವ ಗುರಿಯನ್ನು ಸೇರಿಸಲು ಬೇಕಾದ ಉಳಿದ ಮೊತ್ತವನ್ನು ಗಮನದಲ್ಲಿರಿಸಿಕೊಳ್ಳುತ್ತದೆ. ಆದ್ದರಿಂದ ಪುನರಾವರ್ತಿತ ಕ್ರಿಯೆಯ ಒಳಗೆ, ನಾವು ಎರಡು ಮೂಲ ಪ್ರಕರಣಗಳನ್ನು ಇಡುತ್ತೇವೆ. ಅಗತ್ಯವಿರುವ ಉಳಿದ ಮೊತ್ತವು .ಣಾತ್ಮಕವಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುವುದು ಮೊದಲ ಮೂಲ ಪ್ರಕರಣವಾಗಿದೆ. ಅಂತಹ ಸಂದರ್ಭದಲ್ಲಿ, ನಾವು ಪುನರಾವರ್ತಿತ ಕಾರ್ಯದಿಂದ ಹಿಂತಿರುಗುತ್ತೇವೆ. ಉಳಿದ ಮೊತ್ತವು ಶೂನ್ಯಕ್ಕೆ ಸಮನಾಗಿದ್ದರೆ ಎರಡನೇ ಬೇಸ್ ಕೇಸ್ ನಮ್ಮ ಅಗತ್ಯ ಸ್ಥಿತಿಯಾಗಿದೆ. ಉಳಿದ ಮೊತ್ತ ಶೂನ್ಯವಾಗಿದ್ದರೆ ಇದರರ್ಥ ನಾವು ನಮ್ಮ ಅಗತ್ಯ ಗುರಿಯನ್ನು ತಲುಪಿದ್ದೇವೆ. ಆ ಸಮಯದಲ್ಲಿ, ನಾವು ಪ್ರಸ್ತುತ ತಾತ್ಕಾಲಿಕ ಪೂರ್ಣಾಂಕಗಳ ಪಟ್ಟಿಯನ್ನು ಸರಣಿಗಳ output ಟ್‌ಪುಟ್ ಶ್ರೇಣಿಗೆ ತಳ್ಳುತ್ತೇವೆ.

ಕೋಡ್

ಕಾಂಬಿನೇಶನ್ ಸಮ್ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕಾಗಿ ಸಿ ++ ಕೋಡ್

#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

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎನ್ ^ (ಎಂ / ಟಿ + 1)) ಇಲ್ಲಿ N ಎಂಬುದು ಅಭ್ಯರ್ಥಿಗಳ ಸಂಖ್ಯೆ, ಕೊಟ್ಟಿರುವ ಎಲ್ಲಾ ಪೂರ್ಣಾಂಕಗಳಲ್ಲಿ M ಅತ್ಯಂತ ಚಿಕ್ಕ ಅಭ್ಯರ್ಥಿ, ಮತ್ತು T ಎಂಬುದು ಗುರಿ ಮೌಲ್ಯವಾಗಿದೆ. ಆದ್ದರಿಂದ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಘಾತೀಯವಾಗಿರುತ್ತದೆ ಮತ್ತು ಅಲ್ಗಾರಿದಮ್ ಪುನರಾವರ್ತಿತ ಬ್ಯಾಕ್‌ಟ್ರಾಕಿಂಗ್ ಆಗಿರುವುದರಿಂದ ಇದನ್ನು ನಿರೀಕ್ಷಿಸಲಾಗಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಟಿ / ಎಂ), ಇಲ್ಲಿ ಟಿ ಎಂಬುದು ಗುರಿ ಮೌಲ್ಯವಾಗಿದೆ ಮತ್ತು ಇತರ ಎಲ್ಲ ಅಭ್ಯರ್ಥಿಗಳಲ್ಲಿ ಎಂ ಕನಿಷ್ಠ ಅಂಶವಾಗಿದೆ.