รวมผลรวม Leetcode Solution


ระดับความยาก กลาง
ถามบ่อยใน อะโดบี Airbnb อเมซอน แอปเปิล Atlassian บลูมเบิร์ก ByteDance อีเบย์ Facebook แซคส์โกลด์แมน Google LinkedIn ไมโครซอฟท์ คำพยากรณ์ Snapchat สี่เหลี่ยมด้านเท่า Uber VMware Walmart Labs
แถว ย้อนรอย

ปัญหา Combination Sum 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 จะถูกทำซ้ำ เราสามารถตรวจสอบได้ว่าทั้ง 3 ผลลัพธ์รวมตามเป้าหมายที่กำหนด

แนวทางสำหรับ Combination Sum Leetcode Solution

แนวทางสำหรับปัญหานั้นง่ายต่อการค้นหา โดยทั่วไปในปัญหาเช่นนี้เราจำเป็นต้องใช้การย้อนรอย เนื่องจากในคำถามดังกล่าวเราจำเป็นต้องค้นหาให้ครบถ้วนและพบคำตอบ ก่อนอื่นเราจัดเรียงรายการของจำนวนเต็มที่มอบให้กับเรา หลังจากนั้นเราจะสร้างฟังก์ชันแบบวนซ้ำซึ่งจะช่วยเพิ่มจำนวนเต็มให้กับรายการจำนวนเต็มชั่วคราวในปัจจุบันและติดตามผลรวมที่เหลือที่จำเป็นในการรวมเข้ากับเป้าหมายที่กำหนด ดังนั้นในฟังก์ชันเรียกซ้ำเราจะเก็บฐานสองกรณี กรณีฐานแรกคือการตรวจสอบว่าผลรวมที่เหลือที่ต้องการเป็นลบหรือไม่ ในกรณีนั้นเราจะกลับจากฟังก์ชันเรียกซ้ำ กรณีฐานที่สองเป็นเงื่อนไขที่เราต้องการหากผลรวมที่เหลือเท่ากับศูนย์ หากผลรวมที่เหลือเป็นศูนย์หมายความว่าเราบรรลุเป้าหมายที่ต้องการแล้ว ณ จุดนั้นเราพุชรายการชั่วคราวปัจจุบันของจำนวนเต็มลงในอาร์เรย์เอาต์พุตของอาร์เรย์

รหัส

รหัส 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), โดยที่ T คือค่าเป้าหมายและ M เป็นองค์ประกอบที่น้อยที่สุดในบรรดาตัวเลือกอื่น ๆ ทั้งหมด