thảo luận [Học Tập] Topic thuật toán

thuyduong2007 đã nói:

Sau khi làm bài https://leetcode.com/problems/queue-reconstruction-by-height/
Mình thấy khá là hay. Nên sẽ chia sẻ lại cách mình giải bài này cho mọi người.

Input của bài này có dạng như sau:
[[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]

Đây là một list chứa các list con, mỗi list con sẽ chứa 2 phần tử: mình tạm gọi là a,b.
Yêu cầu của bài này là sắp xếp lại list trên sao cho tại mỗi list con bất kỳ, thì số list con đứng trước nó có giá trị a lớn hơn hoặc bằng giá trị a của nó đúng bằng b. Nghe chỗ này hơi rối đúng k? .
Ví dụ với input là list bên trên, thì output như dưới đây được coi lại hợp lệ:
[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Trước [5,0] không có list nào có phần tử đầu lớn hơn 5.
Trước [7,0] không có list nào có phần tử đầu lớn hơn 7.
Trước [5,2] có đúng 2 list có phần đầu lớn hơn 5.
Trước [6,1] có đúng 1 list có phần đầu lớn hơn 6.
...

Đến đây hi vọng mọi người đã hiểu được yêu cầu của bài toán.

Bài này mình sẽ giải bằng greedy. Nếu ai chưa biết greedy là gì thì có thể tự tìm hiểu hoặc tìm đọc những post của @_Gia_Cat_Luong_ có chia sẻ rồi.

Cách giải của mình trong bài này dựa trên 2 nhận xét quan trọng như sau.

• Giả sử ta đang có một list hợp lệ: l = [[a1,b1],[a2,b2],...,[an,bn]] và một list con [ax,bx] mà ax nhỏ hơn tất cả các phần tử a1,...,an.
  Thì khi ta chèn [ax,bx] vào một vị trí bất kỳ trong l thì luôn cho ra một list hợp lệ.
  VD: [[7,0]] ,[6,1],[9,0],[8,1]] đang hợp lệ, chèn [5,0] vào bất kỳ vị trí nào thì vẫn cho ra một list hợp lệ.
• Đầu ra của bài toán sẽ luôn có dạng như sau: [[a,b1],...,[a,b2],...,[a,b3]]. mà b1,b2,b3 là dãy tăng dần. Nếu không thì sẽ vi phạm yêu cầu bài toán ngay.

Sau khi nhìn ra được 2 điểm này thì mình bắt đầu xây dựng ra solution. Đễ dễ hơn thì mình sẽ đi thẳng vào ví dụ cụ thể.

1. Input:
   [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
2. Sort ra 1 list như sau:
   [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
   (a giảm dần, khi a bằng nhau thì b lại tăng dần)
3. Nếu chỉ dừng lại ở đây thì rõ ràng chưa thỏa mãn điều kiện của bài toán.
   Do đó mình sẽ phải duyệt lại cái list trên.
4. Do list đã được sort nên một list con nằm ở vị trí idx thì sẽ luôn có có idx phần tử có a lớn hơn nó.
   Do đó ta dựa vào idx và giá trị của b để xác định được một list con có cần vi phạm hay không, và nếu nó vi phạm thì sẽ biết được vị trí mới của nó.
   Vd: [[7,0],[7,1],[6,1],[5,0],[5,2],[4,4]]
   idx = 0, duyệt [7,0]: idx <= 0 ? -> true -> output: [[7,0]]
   idx = 1, duyệt [7,1]: idx <= 1? -> true -> output: [[7,0],[7,1]]
   idx = 2, duyệt [6,1]: idx <= 1? -> false -> chèn vào vị trí 1-> output: [[7,0],[6,1],[7,1]]
   idx = 3, duyệt [5,0]: idx <= 0? -> false -> chèn vào vị trí 0-> output: [[5,0],[7,0],[6,1],[7,1]]
   idx = 4, duyệt [5,2]: idx <= 2? -> false -> chèn vào vị trí 2-> output: [[5,0],[7,0],[5,2],[6,1],[7,1]]
   idx = 5, duyệt [4,4]: idx <= 4? -> false -> chèn vào vị trí 4-> output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
5. Đến đây là đã hoàn tất.

Còn đây là code C++ của mình.

C++:

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), [] (auto a, auto b) {
            return a[0] == b[0] ? a[1] < b[1] : a[0] > b[0];
        });
      
        list<vector<int>> list_people;
        for(int i = 0; i < people.size(); i++){
            if (i > people[i][1]){
                auto it = list_people.begin();
                std::advance(it, people[i][1]);
                list_people.insert(it, move(people[i]));
            } else{
                list_people.push_back(move(people[i]));
            }
        }
        people.clear();
        people.insert(people.begin(), list_people.begin(), list_people.end());
        return people;
    }
};

@_Gia_Cat_Luong_ : cách của thím có giống như t k?

Nhấp để mở rộng...

• Mình sẽ tìm cách list những thằng này theo thứ tự hợp lý để append vào mảng output
• Bước đầu tiên là tìm danh sách những thằng phù hợp để insert vào vị trí tiếp theo. Ví dụ vị trí đầu tiên thì lấy ra những thằng có tallerCount = 0. Vị trí số 1 thì lấy ra những thằng có tallerCount = 1 và thấp hơn hoặc bằng thằng trước hoặc tallerCount = 0 và cao hơn thằng trước. Khá brute-force. Bước này O(nlogn)
• Sau đó insert thằng có chiều cao thấp nhất trong list lọc được ở trên vào mảng output (greedy)
• Lặp lại đến khi nào insert hết vào mảng output là xong

from sortedcontainers import SortedList

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        n = len(people)
        people.sort(key=lambda pp: pp[0])
        queuedIndex = set()
        queuedHeights = SortedList()
        queue = []
       
        while len(queue) < n:
            ppIndex = self.findSuitablePeopleIndex(people, queuedIndex, queuedHeights)
            if ppIndex < 0:
                raise Error('Queue is not reconstructable; current queue: ' + queue)
               
            queue.append(people[ppIndex])
            queuedIndex.add(ppIndex)
            queuedHeights.add(people[ppIndex][0])
           
        return queue
   
    def findSuitablePeopleIndex(self, people, queuedIndex, queuedHeights):
        for i, pp in enumerate(people):
            if i in queuedIndex or pp[1] > len(queuedIndex):
                continue

            heightIndex = queuedHeights.bisect_left(pp[0])
            if len(queuedHeights) - heightIndex == pp[1]:
                return i

        return None

• 1 <= nums.length <= 1000: O(n^2)
• 1 <= m <= min(50, nums.length): Có vẻ là solution sẽ tăng theo hàm mũ O(2^m)
• Ta thấy bài toán có tính đệ quy. Để tìm được cách chia array thành m đoạn sao cho có tổng lớn nhất là nhỏ nhất. Ta có thể quy việc giải bài toán con nhỏ hơn.
• Giả sử ta đã tìm được đoạn đầu tiên của nghiệm tối ưu là từ 0->i. Vậy bài toán trở thành chia đoạn từ (i + 1)->n thành (m - 1) đoạn nhỏ hơn sao cho tối ưu.
• Điều kiện dừng là khi m = 1, ta chỉ việc trả về tổng của mảng đang xét. Vì không còn gì để chia nữa.
• Nhưng vấn đề là làm ta tìm được đoạn 0->i của nghiệm tối ưu. Well, thật ra ta sẽ xét từng trường hợp xem cái nào tối ưu nhất thì giữ lại.
• Dĩ nhiên là áp dụng memoization để tránh giải lại bài toán con gối nhau

• Viết hàm trySplitArray(i, m). Để giải bài toán tương tự nhưng cho array từ khoảng thứ i->n, và chia thành m phần.
• Điều kiện neo là m = 1 thì trả về tổng từ i -> n luôn
• Khởi tạo nghiệm tối ưu bằng MAX_INT
• Thử với mỗi j trong khoảng từ i -> n
  • Giả sử đoạn đầu ta đã biết là từ i -> j, ta tính và lưu lại tổng này
  • Giải bài toán đệ quy nhỏ cho đoạn phía sau trySplitArray(j + 1, m - 1)
  • Tính tổng lớn nhất cho trường hợp này = max của 2 case bên trên
  • Nếu tổng lớn nhất này nhỏ hơn nghiệm tối ưu => update lại nghiệm tối ưu bằng giá trị này
• Trả về nghiệm tối ưu
• Dễ thấy đáp án bài toán lớn là kết quả của hàm trên với i = 0 và m = m input

class Solution:
    def splitArray(self, nums: List[int], m: int) -> int:
        if m >= len(nums):
            return max(nums)
    
        suffixSum = []
        s = 0
        for i in range(len(nums) - 1, -1, -1):
            s += nums[i]
            suffixSum.append(s)
    
        suffixSum.reverse()
        self.suffixSum = suffixSum
        self.nums = nums
    
        return self.trySplitArray(0, m)
 
    @cache
    def trySplitArray(self, i, m):
        if m <= 1:
            return self.suffixSum[i]
    
        largestSum = math.inf
        s = 0
        while i + m <= len(self.nums):
            s += self.nums[i]
            if s >= largestSum:
                break
            
            largestSum = min(largestSum, max(s, self.trySplitArray(i + 1, m - 1)))
            i += 1
        
        return largestSum

• Solution này chưa tối ưu, chỉ faster than 20% thôi. Mình cũng chưa có thời gian để check thêm. Bạn nào có cách giải tốt hơn xin hãy chia sẻ .
• Đoạn code có hơi khác với solution một chút, bổ sung một vài trick nhằm tối ưu thêm. Nhưng ý tưởng cơ bản thì vẫn vậy.

_Gia_Cat_Luong_ đã nói:

Hông, cách của tui cùi bắp hơn, mặc dù cũng là greedy, ý tưởng chính:

• Mình sẽ tìm cách list những thằng này theo thứ tự hợp lý để append vào mảng output
• Bước đầu tiên là tìm danh sách những thằng phù hợp để insert vào vị trí tiếp theo. Ví dụ vị trí đầu tiên thì lấy ra những thằng có tallerCount = 0. Vị trí số 1 thì lấy ra những thằng có tallerCount = 1 và thấp hơn hoặc bằng thằng trước hoặc tallerCount = 0 và cao hơn thằng trước. Khá brute-force. Bước này O(nlogn)
• Sau đó insert thằng có chiều cao thấp nhất trong list lọc được ở trên vào mảng output (greedy)
• Lặp lại đến khi nào insert hết vào mảng output là xong

=> Độ phức tạp O(nlogn), faster than 20% thôi, at least it works . Cách của ông là chuẩn rồi, sau tui vào discuss cũng thấy nhiều người làm như vậy. Good job mai fen.

Python:

from sortedcontainers import SortedList

class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        n = len(people)
        people.sort(key=lambda pp: pp[0])
        queuedIndex = set()
        queuedHeights = SortedList()
        queue = []
     
        while len(queue) < n:
            ppIndex = self.findSuitablePeopleIndex(people, queuedIndex, queuedHeights)
            if ppIndex < 0:
                raise Error('Queue is not reconstructable; current queue: ' + queue)
             
            queue.append(people[ppIndex])
            queuedIndex.add(ppIndex)
            queuedHeights.add(people[ppIndex][0])
         
        return queue
 
    def findSuitablePeopleIndex(self, people, queuedIndex, queuedHeights):
        for i, pp in enumerate(people):
            if i in queuedIndex or pp[1] > len(queuedIndex):
                continue

            heightIndex = queuedHeights.bisect_left(pp[0])
            if len(queuedHeights) - heightIndex == pp[1]:
                return i

        return None

Rất vui vì ông đã chia sẻ nha, có người share chung mỗi ngày thấy cũng vui chứ làm một mình mãi cũng hơi oải .

Nhấp để mở rộng...

• tìm số thứ k trong các số trong ds
• xóa 1 số bất kì

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<class T> using set_order = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    auto n = people.size();
    vector<pair<int,int>> v;
    v.reserve(n);
    for(auto& p:people) v.emplace_back(p[0],p[1]);
    vector<vector<int>> res(n);
    sort(v.begin(),v.end(),[](const pair<int,int>& a,const pair<int,int>& b){
        return a.first == b.first ? a.second > b.second : a.first < b.first;
    });
    set_order<int> st;
    for(int i=0;i<n;i++) st.insert(i);
    for(auto p:v){
        auto ptr = st.find_by_order(p.second);
        res[*ptr].push_back(p.first),res[*ptr].push_back(p.second);
        st.erase(ptr);
    }
    return res;
}
};

clonemasteruwu đã nói:

cách của bác trước là O(n^2) đó. (Worst case: (n,0) (n,1) (n-1,1) (n-1,2) ...
lí do là bác xài linkedlist và advance để tìm vị trí.
mình làm ngược lại 1 chút (đi từ những thằng nhỏ nhất)
đưa về 1 bài toán đơn giản hơn là thiết kế 1 data structure:

• tìm số thứ k trong các số trong ds
• xóa 1 số bất kì

bài này code = sum segment tree thì sẽ có best performance, tuy nhiên do mình lười nên giới thiệu 1 con hàng xài tạm là gnu-pbds (policy base data structure, custom data structure cho tree/hash table)
tại sao? vì set/map của c++ k có tìm key dựa trên order/ tìm order dựa trên key.
Disadvantage: big constant performance (x2-> x3 tùy giới hạn)

C++:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

template<class T> using set_order = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    auto n = people.size();
    vector<pair<int,int>> v;
    v.reserve(n);
    for(auto& p:people) v.emplace_back(p[0],p[1]);
    vector<vector<int>> res(n);
    sort(v.begin(),v.end(),[](const pair<int,int>& a,const pair<int,int>& b){
        return a.first == b.first ? a.second > b.second : a.first < b.first;
    });
    set_order<int> st;
    for(int i=0;i<n;i++) st.insert(i);
    for(auto p:v){
        auto ptr = st.find_by_order(p.second);
        res[*ptr].push_back(p.first),res[*ptr].push_back(p.second);
        st.erase(ptr);
    }
    return res;
}
};

Nhấp để mở rộng...

clonemasteruwu đã nói:

vì set/map của c++ k có tìm key dựa trên order/ tìm order dựa trên key.

Nhấp để mở rộng...

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
    auto n = people.size();
    vector<pair<int,int>> v;
    v.reserve(n);
    for(auto& p:people) v.emplace_back(p[0],p[1]);
    vector<vector<int>> res(n);
    sort(v.begin(),v.end(),[](const pair<int,int>& a,const pair<int,int>& b){
        return a.first == b.first ? a.second > b.second : a.first < b.first;
    });
    set<int> st;
    for(int i=0;i<n;i++) st.insert(i);
    for(auto p:v){
        auto ptr = st.begin();
        advance(ptr, p.second);
        res[*ptr].push_back(p.first),res[*ptr].push_back(p.second);
        st.erase(ptr);
    }
    return res;
}
};

thuyduong2007 đã nói:

Cái này không đúng nha. Do set/map trong stl được implement bằng red-black tree. Nên 2 tác vụ này hoàn toàn khả thi nhé.

Nhấp để mở rộng...

• 1 <= nums.length <= 200: O(n^3) hoặc O(2^n) chăng
• Trước tiên, ta thấy để có thể chia được thành 2 phần có tổng bằng nhau tổng của mảng input phải là số chẵn
• Giả sử ta có thể chia một mảng thành 2 phần có tổng bằng nhau. Thì mỗi tổng của mỗi phần đó sẽ bằng bao nhiêu ? Dễ thấy là bằng sum / 2
• Vậy làm sao tìm được 2 phần này ? Có lẽ không cần tìm cả 2, ta chỉ cần tìm một phần có tổng đúng bằng sum / 2 là đủ
• Làm sao để tìm được tập con này ? Tổng số tập con của một tập có n phần tử là 2^n. Ta dĩ nhiên không thể brute-force để check cả 2^200 trường hợp.
• Tương tự như bài trước, một trong những cách thường gặp là sử dụng quy hoạch động. Ta thử tìm cách giải bài toán này bằng cách đưa về việc giải các bài toán con nhỏ hơn.
• Các bước suy luận để nghĩ ra đáp án có bạn có thể thực hiện giống như bài trước: https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/post-11139826
• Và các bạn sẽ thấy 2 bài này thực ra là một, chỉ là một bên cho phép lặp lại các phần tử, còn một bên thì không.

• Viết hàm hasSubSetWithSum(i, s) để kiểm tra xem có thể tạo tập con có tổng đúng bằng s từ mảng nums[i:n] hay không
• Dễ thấy nếu phần num bằng s thì đáp án là True, đây cũng là điều kiện dừng (Một điều kiện dừng khác là duyệt hết mảng mà không thấy kết quả phù hợp => False)
• Ngược lại, ta sẽ thấy tập con cần tìm này (giả sử tồn tại) hoặc chứa nums hoặc không. Do đó ta kiểm tra 2 trường hợp:
  • Giả sử tập con cần tìm chứa nums[ i ] => Ta sẽ cần tìm một tập con trong khoảng nums[i + 1:n] sao cho tổng bằng s - nums[ i ] (Cần để ý s > nums[ i ] vì mảng chỉ chứa số dương)
  • Giả sử tập con cần tìm không chứa nums[ i ] => Ta sẽ cần tìm một tập con trong khoảng nums[i + 1:n] sao cho tổng bằng s
• Nếu cả 2 cách đều không khả thi => Vậy đáp án trong trường hợp này là không khả thi
• Đáp án của bài toán chính là kết quả của hasSubSetWithSum(0, sum(nums) / 2)
• Dĩ nhiên là phải áp dụng memoization để tránh giải lại các bài toán con

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)
        if s % 2 != 0:
            return False
      
        self.nums = nums
        return self.hasSubSetWithSum(0, s // 2)
  
    @cache
    def hasSubSetWithSum(self, i, s):
        if i >= len(self.nums):
            return False
      
        if self.nums[i] == s:
            return True
      
        if self.nums[i] < s and self.hasSubSetWithSum(i + 1, s - self.nums[i]):
            return True
      
        if self.hasSubSetWithSum(i + 1, s):
            return True
      
        return False

clonemasteruwu đã nói:

tại sao? vì set/map của c++ k có tìm key dựa trên order/ tìm order dựa trên key.

Nhấp để mở rộng...

thuyduong2007 đã nói:

Cái này không đúng nha. Do set/map trong stl được implement bằng red-black tree. Nên 2 tác vụ này hoàn toàn khả thi nhé.

Nhấp để mở rộng...

clonemasteruwu đã nói:

nó khả thi với độ phức tạp như thế nào thôi chắc b chưa xem cái worst case mình propose nhỉ b biết advance của set/map có đpt như nào k

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Tiếp tục chuyên mục mỗi ngày một leetcode. 3 bài mình làm ngày hôm nay:

#375. (Medium) https://leetcode.com/problems/guess-number-higher-or-lower-ii/
#376. (Medium) https://leetcode.com/problems/wiggle-subsequence/
#377. (Medium) https://leetcode.com/problems/combination-sum-iv/

Mình sẽ share về bài Combination Sum IV:
#377. (Medium) https://leetcode.com/problems/combination-sum-iv/

Phân tích bài toán:

• 1 <= nums.length <= 200: Với limit nhỏ như thế này thì có 2 khả năng:
  • Hoặc là độ phức tạp để giải rất cao O(2^n) hoặc thậm chí là O(n!)
  • Hoặc là kết quả output rất lớn. Nên nếu để limit quá cao sẽ bị tràn số
• Để biết là dạng nào thì ta có thể thử chạy test với input lớn một tí:
  • Nếu chạy lâu và ra kết quả là một số nhỏ => Trường hợp 1. Lúc này giải pháp tối ưu có lẽ là vét cạn. Các thuật toán phù hợp thường là liệt kê hoặc quay lui.
  • Nếu chạy nhanh nhưng ra kết quả là một số rất lớn => Trường hợp 2. Lúc này hướng giải thì hên xui, nhưng hay gặp nhất chắc là quy hoạch động.
• Quay lại bài này, ta thấy chỉ cần tăng input lên hơi to một chút là gặp ngay lỗi:

• => Có vẻ là hướng thứ 2, vậy ta thử giải bài này bằng QHĐ

Một chút về Quy Hoạch Động:

• Mình biết với nhiều người thuật toán QHĐ là một cái gì đó cao siêu, và dường như chỉ có các bậc thánh nhân chuyên tin mới nghĩ ra cách giải.
• Cách đây 1 năm mình cũng nghĩ vậy. Nhưng sau một thời gian cày cuốc và làm quen với dạng bài này, thì mình thấy nó cũng k có gì quá cao siêu.
• Chỉ cần nắm vững hướng tư duy và pattern của nó thì có thể vận dụng trong hầu hết các trường hợp. (Dĩ nhiên trừ những bài quá khó - mình cũng bó tay và vào discuss để xem như mn thôi. Kakaka)
• Với bạn nào chưa quen thì mình suggest xem clip này về QHĐ. Đây cũng là clip giúp mình làm quen với thuật toán này:

• Về cơ bản, pattern của thuật toán QHĐ tương tự như đệ quy, hay chia để trị. Đó là kết quả của bàn toán lớn được tính từ kết quả của các bài toán con, và tiếp tục đệ quy như thế cho đến trường hợp cơ bản đã biết trước.
• Cần chú ý là một bài toán giải bằng QHĐ cần có 2 tính chất:
  • Các bài toán con phải gối nhau: Thì việc lưu lại kết quả của các bài toán con mới có ý nghĩa tối ưu. Không thì nó chỉ là chia để trị thôi.
  • Cấu trúc con tối ưu: Kết quả tối ưu của bài toán lớn phải tính được từ kết quả tối ưu của các bài toán con. Nếu không thì có lưu lại kết quả của bài toán con cũng vô nghĩa.

Quay lại bài toán, ta thử áp dụng cách tiếp cận QHĐ để giải bài này:

• Để đếm số lượng các combinations có tổng bằng target, ta có thể tính nó từ kết quả của bài toán con hay không ?
• Vậy bài toán con ở đây là gì ? Hiểu nôm na đó là bài toán tương tự như bài toán gốc, nhưng với input "nhỏ" hơn
• "Nhỏ" ở đây không nhất thiết là nhỏ hơn về mặt toán học. Mà là input đó "gần" với "trường hợp cơ bản" hơn.
• "Trường hợp cơ bản" có nghĩa là các trường hợp mà từ đó ta có thể suy ra kết quả ngay lập tức, không cần phải thực hiện việc đưa về bài toán nhỏ hơn nữa.
• Quay lại, trong trường hợp này, bài toán con có thể là:
  • Cũng với mảng input đó, nhưng target là một số nhỏ hơn
  • Vẫn target đó, nhưng input ít đi một / một vài phần tử
• Ở đây ta thấy một phần tử có thể được dùng lại nhiều lần, nên xem ra hướng thứ hai khó khả thi. Nếu follow theo hướng thứ nhất, "target thấp hơn" thì "trường hợp cơ bản" sẽ là gì. Ta cứ nghĩ đến các case đơn giản nhất ?

• Đào sâu thêm một chút thì ta có thể tổng quá hóa thành như thế này:

• Vậy đưa về bài toán nhỏ hơn như thế nào ? Cái này gọi là "công thức truy hồi" và theo mình cũng là phần khó nhất của một bài QHĐ. Làm được hay không là ở chỗ bạn phải nhìn ra công thức này.
• Với mình, cách đơn giản là cứ execute một ví dụ và cố gắng thử tính bài toán lớn từ kết quả bài toán nhỏ. Ví dụ nums = [1, 2, 3]; target = 4:
• Giả sử ta biết số cách tạo ra "target = 3" đi, liệu ta có thể áp dụng nó để tính cho "target = 4" ?
• Đương nhiên có thể, dễ thấy giả sử có n cách để tạo ra "target = 3", ta chỉ việc cộng 1 vào mỗi cách đó để tạo ra "target = 4". Vì có số 1 nằm trong mảng input.
• Ồ. Vậy tổng quát hóa lên, nếu ta biết được có n cách tạo ra "target = x" thì cũng sẽ có n cách để tạo ra "target = k", nếu như "k - x" có nằm trong mảng input.
• Nghĩ ngược lại có vẻ sẽ hay hơn. Ta tính luôn với mỗi số x nằm trong mảng input thì sẽ có thêm combinationSum(k - x) cách để tạo ra số k.
• Nhưng cũng cần chú ý thêm edge case, nếu x = k luôn thì sao, khi đó vẫn có 1 cách để tạo ra số k, là chọn chính nó. Nhưng combinationSum(k - x) sẽ trả về 0 (vì 0 < nums[0]). Thôi thì ta thêm exception cho case này vậy.
• Vậy kết quả là tổng các combinationSum(k - x) với mỗi x trong mảng input.

Solution:

• Mình thích sử dụ Memoization, vì thấy nó gần hơn với suy nghĩ tự nhiên của con người
• Sort lại nums, lưu mảng nums đã sort lại
• Viết hàm đệ quy countCombination để tính
• Nếu target == 0: return 1
• Nếu target < nums[0]: return 0
• Nếu k == nums[0]: return 1
• Nếu target này đã được tính trước đó (nằm trong bảng kết quả), trả kết quả đã tính từ trước
• Tính kết quả bằng tổng các countCombination(k - x) với mỗi x trong mảng input.
• Lưu kết quả lại vào bảng kết quả, chú ý đây là bước quan trọng và thể hiện bản chất của quy hoạch động
• Trả về kết quả đã tính toán

Python:

class Solution:
    def combinationSum4(self, nums: List[int], target: int) -> int:
        nums.sort()
        self.nums = nums
        return self.countCombination(target, {})
  
    def countCombination(self, target, memo):
        if target == 0:
            return 1
        if target < self.nums[0]:
            return 0
        if target == self.nums[0]:
            return 1
      
        if target in memo:
            return memo[target]
      
        memo[target] = sum(self.countCombination(target - x, memo) for x in self.nums)
        return memo[target]

p/s: Bài này thật ra khá kinh điển. Mình cố ý chọn nó và viết chi tiết để các bạn mới có thể học được cách tư duy và hướng phát triển vấn đề, thay vì chỉ đưa solution. Đồng thời solution bên trên chỉ đạt mức "faster than 11%". Nghĩa là còn có nhiều điểm có thể tối ưu cũng như viết gọn lại. Các bạn cứ đóng góp thoải mái. Welcome.

Nhấp để mở rộng...

class Solution {
public:
   
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum%2 != 0) return false;
        return isContainSubset(nums, 0, sum/2);
    }
   
    bool isContainSubset(const vector<int>& nums, int pos, int target) {
        if (target == 0) return true;
        if (target < 0 || pos >= nums.size()) return false;
       
        return isContainSubset(nums, pos + 1, target)
                || isContainSubset(nums, pos + 1, target - nums[pos]);
    }
};

• Mỗi lần cần lấy kết quả nó sẽ cần 2 lần tính hash -> tốn gian
• Có quá nhiều hash table và có thể có nhiều bucket không được dùng -> tốn mem

class Solution {
public:
   
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum%2 != 0) return false;
        unordered_map<int, bool> cache;
        return isContainSubset(nums, cache, 0, sum/2);
    }
   
    bool isContainSubset(const vector<int>& nums, unordered_map<int, bool> &cache, int pos, int target) {
        if (target == 0) return true;
        if (target < 0 || pos >= nums.size()) return false;
       
        auto it1 = cache.find(getKey(pos, target));
        if (it1 != cache.end()){
            return it1->second;
        }
       
        bool result = isContainSubset(nums, cache, pos + 1, target)
                || isContainSubset(nums, cache, pos + 1, target - nums[pos]);
        cache[getKey(pos, target)] = result;
       
        return result;
    }
   
    int getKey(int pos, int target){
        return target*201 + pos;
    }
};

1. Khi mình liên tục insert vào unordered_map, thì đến một mức nhất định nó sẽ cần phải rehash. Do đó để tránh việc rehash thì mình sẽ cố gắng estimate số lượng cặp {pos,target}. Cần lưu ý là nếu mình estimate quá nhỏ thì có thể nó vẫn cần rehash, ngược lại nếu mình estimate quá lớn thì lại tốn mem. Qua thử nghiệm thì mình thấy giá trị dưới đây là hợp lý.
   unordered_map<int, bool> cache
   -> unordered_map<int, bool> cache(nums.size()*nums.size());
2. Ngoài ra có một điểm có thể improve:
   bool result = isContainSubset(nums, cache, pos + 1, target) || isContainSubset(nums, cache, pos + 1, target - nums[pos]);
   Hầu hết ngôn ngữ phổ biến đều có support short-circuit. Tức là với toán tử or, nếu biểu thức đầu tiên là true rồi thì nó sẽ không làm nữa mà sẽ trả ra true luôn. Phép toán and thì ngược lại. Sau khi thử đổi lại thành:
   bool result = isContainSubset(nums, cache, pos + 1, target - nums[pos]) || isContainSubset(nums, cache, pos + 1, target);
   Thì kết quả cho ra tốt hơn hẳn.

thuyduong2007 đã nói:

Hôm nay mình sẽ chia sẻ cách mình xây dựng một giải pháp cũng như tối ưu nó bằng C++.
Cụ thể là về bài toán này: https://leetcode.com/problems/partition-equal-subset-sum/submissions/

Cách tiếp cận ban đầu của mình cũng khá giống @_Gia_Cat_Luong_ ở post này:
https://voz.vn/t/hoc-tap-topic-thuat-toan.182659/page-24#post-11391237

Khi đó code sẽ như sau:

C++:

class Solution {
public:
 
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum%2 != 0) return false;
        return isContainSubset(nums, 0, sum/2);
    }
 
    bool isContainSubset(const vector<int>& nums, int pos, int target) {
        if (target == 0) return true;
        if (target < 0 || pos >= nums.size()) return false;
    
        return isContainSubset(nums, pos + 1, target)
                || isContainSubset(nums, pos + 1, target - nums[pos]);
    }
};

Đến đây độ phức tạp của bài toán sẽ là n!. Chắc chắn sẽ bị timeout. Để giải quyết chuyện này thì mình sẽ phải cache kết quả của hàm isContainSubset cho từng cặp pos, target. Mục đích là để sử dụng lại kết quả đã được tính trước đó.
Với python thì chỉ cần thêm @cache vào là xong, quá easy.
Nhưng mà C++ thì không có, hoặc có mà mình chưa biết, . Nên phải tự tạo 1 cái cache riêng. với input, output giống như isContainSubset (ngoại trừ nums). Khi đó cache sẽ như sau:
unordered_map<int, unordered_map<int, bool>> cache; // cache[pos][target] -> result
Tuy nhiên, cách khai báo Cache như thế này sẽ có 2 vấn đề:

• Mỗi lần cần lấy kết quả nó sẽ cần 2 lần tính hash -> tốn gian
• Có quá nhiều hash table và có thể có nhiều bucket không được dùng -> tốn mem

Cách giải quyết là khai báo một unordered_map với multiple keys.
https://stackoverflow.com/questions...-keys-with-map-unordered-map-multidimensional

Tuy nhiên mình thấy cách này vẫn phức tạp, nên sẽ dùng một cách đơn giản hơn nữa để áp dụng cho bài này. Do điều kiện ban đầu: 1 <= nums.length <= 200 => pos < 201. Dựa vào điểm này mình sẽ tính lại: key = target*201 + pos. và dùng key này để access cái cache.
Khi đó code sẽ như sau:

C++:

class Solution {
public:
 
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum%2 != 0) return false;
        unordered_map<int, bool> cache;
        return isContainSubset(nums, cache, 0, sum/2);
    }
 
    bool isContainSubset(const vector<int>& nums, unordered_map<int, bool> &cache, int pos, int target) {
        if (target == 0) return true;
        if (target < 0 || pos >= nums.size()) return false;
    
        auto it1 = cache.find(getKey(pos, target));
        if (it1 != cache.end()){
            return it1->second;
        }
    
        bool result = isContainSubset(nums, cache, pos + 1, target)
                || isContainSubset(nums, cache, pos + 1, target - nums[pos]);
        cache[getKey(pos, target)] = result;
    
        return result;
    }
 
    int getKey(int pos, int target){
        return target*201 + pos;
    }
};

Đến đây mình thấy còn có thể optimize thêm.

1. Khi mình liên tục insert vào unordered_map, thì đến một mức nhất định nó sẽ cần phải rehash. Do đó để tránh việc rehash thì mình sẽ cố gắng estimate số lượng cặp {pos,target}. Cần lưu ý là nếu mình estimate quá nhỏ thì có thể nó vẫn cần rehash, ngược lại nếu mình estimate quá lớn thì lại tốn mem. Qua thử nghiệm thì mình thấy giá trị dưới đây là hợp lý.
   unordered_map<int, bool> cache
   -> unordered_map<int, bool> cache(nums.size()*nums.size());
2. Ngoài ra có một điểm có thể improve:
   bool result = isContainSubset(nums, cache, pos + 1, target) || isContainSubset(nums, cache, pos + 1, target - nums[pos]);
   Hầu hết ngôn ngữ phổ biến đều có support short-circuit. Tức là với toán tử or, nếu biểu thức đầu tiên là true rồi thì nó sẽ không làm nữa mà sẽ trả ra true luôn. Phép toán and thì ngược lại. Sau khi thử đổi lại thành:
   bool result = isContainSubset(nums, cache, pos + 1, target - nums[pos]) || isContainSubset(nums, cache, pos + 1, target);
   Thì kết quả cho ra tốt hơn hẳn.

Sau khi áp dụng hết những cách trên thì solution của mình beats gần 90%.

Nhấp để mở rộng...

• dùng std:: pair: Cách này universal, k cần phải để ý gì constraint, bù lại performance k tốt bằng cách hiện tại
• dùng bit manipulation: key = target << 16 | pos. Cũng gần giống như cách *201, nhưng là bitwise nên có lẽ sẽ nhanh hơn

_Gia_Cat_Luong_ đã nói:

Mình lâu lắm rồi không code C++ nhưng theo mình nhớ chỗ key có thể làm bằng 2 cách khác:

• dùng std:: pair: Cách này universal, k cần phải để ý gì constraint, bù lại performance k tốt bằng cách hiện tại
• dùng bit manipulation: key = target << 16 | pos. Cũng gần giống như cách *201, nhưng là bitwise nên có lẽ sẽ nhanh hơn

Một chút tối ưu cho bài này nữa, là 1 trong 2 set cần tìm chắc chắn sẽ có 1 cái chứa phần tử lớn nhất. Nên ta có thể loại nó ra (swap với index 0) và tìm subSet có tổng bằng target - max từ index 1. Nhanh hơn xíu xiu.

Nhấp để mở rộng...

1. Mình đã thử dùng std:: pair rồi nhé. Nó chỉ work với map thôi, unordered_map thì không. Nếu vẫn muốn dùng pair thì phải provide hàm hash mới, có thể work với pair.
2. Chỗ này mình quên mất vụ dùng bit maniputation, mình đã thử và nó chạy nhanh hơn 1 chút nhé. Tuy nhiên chỉ cần dịc 8 bit thôi, do 0 <= pos < 200.

thuyduong2007 đã nói:

1. Mình đã thử dùng std:: pair rồi nhé. Nó chỉ work với map thôi, unordered_map thì không. Nếu vẫn muốn dùng pair thì phải provide hàm hash mới, có thể work với pair.
2. Chỗ này mình quên mất vụ dùng bit maniputation, mình đã thử và nó chạy nhanh hơn 1 chút nhé. Tuy nhiên chỉ cần dịc 8 bit thôi, do 0 <= pos < 200.

Việc loại phần tử max trước khi tìm subset mình cũng nghĩ nó k giúp được quá nhiều. Vì mình còn tốn thêm thời gian O(n) để tìm nó nữa. Hơn nữa việc bạn loại ra cái max có thể làm cho việc tìm kiếm mất tgian hơn. Vd: mình có 2 subset có tổng bằng target: s1 ={x1,x2,...,xn}, s2={y1,y2,...,yn,max}
Nếu bạn loại max trước khi tìm thì chương trình bắt buộc phải tìm được s2'={y1,y2,...,yn} thì mới được dừng lại.
Ngược lại nếu bạn không loại max ra, thì chương trình sẽ dừng lại ngay khi tìm được s1 hoặc s2. Tùy vào testcase mà việc tìm được s1 có thể nhanh hơn việc tìm được s2'.

Dù sao mình cũng cảm ơn bạn đã nhận xét nhé.

Nhấp để mở rộng...

return isContainSubset(nums, pos + 1, target)
                || isContainSubset(nums, pos + 1, target - nums[pos]);

_Gia_Cat_Luong_ đã nói:

mục tiêu greedy là target càng thấp thì càng nhanh tìm ra kết quả.

Nhấp để mở rộng...

return isContainSubset(nums, pos + 1, target - nums[pos])
                || isContainSubset(nums, pos + 1, target);

thuyduong2007 đã nói:

Cái này nếu suy nghĩ kỹ bạn sẽ thấy nó không hoàn toàn đúng. Giả list là [8,7,9,6], target là 15. cách thông thường thì chỉ cần duyệt 8,7 là stop.
Cách của bạn lấy max rồi swap với phần tử đầu: [9,7,8,6] khi đó bạn phải duyệt đến phần tử cuối cùng mới lấy được target 15. Nếu phân tích kỹ chỗ này sẽ thấy cost nó lớn hơn cách thông thường.

Code mình sau khi improve thì đã đổi lại thứ tự rồi nhé. Bạn coi lại chỗ mình nói về short circuit. Bạn nên test với code này.

C++:

return isContainSubset(nums, pos + 1, target - nums[pos])
                || isContainSubset(nums, pos + 1, target);

Nhấp để mở rộng...

_Gia_Cat_Luong_ đã nói:

Chính xác luôn bạn, nên thế mới nói là nó greedy, dĩ nhiên sẽ có worse case nhưng generally thì target thấp sẽ nhanh hơn target cao.
Đoạn short circuit mình có đọc, nhưng nó cũng klq tới ý mình nói. Ví dụ như đoạn sau khi bạn sửa thì chắn chắn subset chứa nums[0] sẽ được chọn. Nếu vậy sao k để nums[0] là số lớn nhất .

Nhấp để mở rộng...

Lập Trình Viên Số Khổ đã nói:

@_Gia_Cat_Luong_ Thuật toán LCS có tìm được tất cả các subsequence có độ dài lớn nhất ko nhỉ, tức in ra tất cả các bộ giống nhau nhưng có độ dài lớn nhất ấy

Nhấp để mở rộng...

thuyduong2007 đã nói:

Có nhé bạn.

Nhấp để mở rộng...