បន្សំសូលុយស្យុងសឺឡែនកូដ


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ កម្មវិធី Adob ​​e Airbnb ក្រុមហ៊ុន Amazon ផ្លែប៉ោម Atlassian ទីភ្នាក់ងារ Bloomberg ByteDance របស់ eBay Facebook ក្រុមហ៊ុន Goldman Sachs ក្រុមហ៊ុន google LinkedIn ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle Snapchat ការ៉េ Uber VMware បន្ទប់ពិសោធន៍វ៉លម៉ាត
អារេ បទថយក្រោយ

ការបូកបញ្ចូលគ្នានៃដំណោះស្រាយបញ្ហាឡេឡៃកូដកូដផ្តល់ឱ្យយើងនូវអ៊ីនធឺណេត អារេ ឬបញ្ជីចំនួនគត់និងគោលដៅ។ យើងត្រូវបានប្រាប់ឱ្យរកការរួមបញ្ចូលគ្នាដែលអាចត្រូវបានធ្វើឡើងដោយប្រើចំនួនគត់ទាំងនេះគ្រប់ពេលវេលាដែលបន្ថែមដល់គោលដៅដែលបានផ្តល់ឱ្យ។ ដូច្នេះជាផ្លូវការយើងអាចប្រើចំនួនគត់ដែលបានផ្តល់ចំនួនដងដែលពួកគេបន្ថែមទៅគោលដៅដែលបានផ្តល់។ លទ្ធផលដែលត្រូវការគឺជាបន្សំដែលមានផលបូកស្មើនឹងគោលដៅដែលបានផ្តល់។

ឧទាហរណ៍បន្សំសូលុយស្យុងសឺឡែនកូដ

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 ត្រូវបានធ្វើម្តងទៀត។ យើងអាចផ្ទៀងផ្ទាត់ថារាល់លទ្ធផលទាំង ៣ បូកនឹងគោលដៅដែលបានផ្តល់ឱ្យ។

វិធីសាស្រ្តសម្រាប់ដំណោះស្រាយបន្សំឡេឡេលេខកូដ

វិធីសាស្រ្តសម្រាប់បញ្ហាគឺសាមញ្ញក្នុងការស្វែងរក។ ជាទូទៅនៅក្នុងបញ្ហាបែបនេះយើងត្រូវបានគេតម្រូវឱ្យប្រើបទភ្លេង។ ដោយសារតែនៅក្នុងសំណួរបែបនេះយើងតម្រូវឱ្យធ្វើការស្វែងរកពេញលេញនិងស្វែងរកចម្លើយ។ ដូច្នេះដំបូងយើងតម្រៀបបញ្ជីចំនួនគត់ដែលត្រូវបានផ្តល់ឱ្យយើង។ បន្ទាប់មកយើងបង្កើតមុខងារហៅខ្លួនឯងដែលបន្តបញ្ចូលលេខគត់ទៅក្នុងបញ្ជីបណ្តោះអាសន្នបច្ចុប្បន្ននៃចំនួនគត់និងតាមដានចំនួនសរុបដែលនៅសល់ដើម្បីបន្ថែមដល់គោលដៅដែលបានផ្តល់។ ដូច្នេះនៅខាងក្នុងមុខងារហៅខ្លួនឯងយើងរក្សាទុកករណីគោលពីរ។ ករណីមូលដ្ឋានដំបូងគឺត្រូវពិនិត្យមើលថាតើការបូកដែលនៅសល់ត្រូវការអវិជ្ជមានឬអត់។ ក្នុងករណីនោះយើងនឹងត្រលប់ពីមុខងារហៅខ្លួនឯងវិញ។ ករណីមូលដ្ឋានទី ២ គឺជាលក្ខខ័ណ្ឌដែលយើងត្រូវការប្រសិនបើផលបូកនៅសល់ស្មើសូន្យ។ ប្រសិនបើផលបូកនៅសល់គឺសូន្យនេះមានន័យថាយើងបានទៅដល់គោលដៅដែលយើងចង់បានហើយ។ នៅចំណុចនោះយើងរុញបញ្ជីបណ្តោះអាសន្នបច្ចុប្បន្ននៃចំនួនគត់ទៅក្នុងលទ្ធផលនៃអារេ។

លេខកូដ

លេខកូដ 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

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (N ^ (M / T + 1)) ដែល N ជាចំនួនបេក្ខជន M ជាបេក្ខជនតូចបំផុតក្នុងចំណោមចំនួនគត់ដែលបានផ្តល់ហើយ T ជាតម្លៃគោលដៅ។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាគឺមាននិទស្សន្តហើយនេះត្រូវបានគេរំពឹងទុកពីព្រោះក្បួនដោះស្រាយគឺការនិយាយឡើងវិញ។

ភាពស្មុគស្មាញនៃលំហ

O (T / M), ដែល T ជាតម្លៃគោលដៅហើយ M គឺជាធាតុអប្បបរមាក្នុងចំណោមបេក្ខជនដទៃទៀត។