Biểu diễn tổng các số Fibonaci

def fib(n):
    """Tính toán số thứ n trong dãy Fibonacci."""
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)

def can_sum_to_n(n):
    """Kiểm tra xem n có thể biểu diễn dưới dạng tổng của các số Fibonacci khác nhau hay không."""
    fib_numbers = []
    i = 0
    # Tính toán các số Fibonacci nhỏ hơn hoặc bằng n và đưa chúng vào một mảng
    while True:
        fib_i = fib(i)
        if fib_i > n:
            break
        fib_numbers.append(fib_i)
        i += 1

    # Sử dụng phương pháp quy hoạch động để tìm các tổng con của các số trong mảng fib_numbers
    possible_sums = {0}
    for num in fib_numbers:
        new_sums = set()
        for s in possible_sums:
            new_sums.add(s + num)
        possible_sums |= new_sums

    # Kiểm tra xem có tồn tại một tổng con bằng n hay không
    return n in possible_sums and len(possible_sums) > 1

# Ví dụ sử dụng
print(can_sum_to_n(7)) # True (vì 7 = 5 + 2)
print(can_sum_to_n(10)) # True (vì 10 = 8 + 2)
print(can_sum_to_n(12)) # False (không có tổng con nào bằng 12)

#include <iostream>
#include <vector>
#include <unordered_set>

using namespace std;

int fib(int n) {
    // Tính toán số thứ n trong dãy Fibonacci bằng thuật toán đệ quy
    if (n < 2) {
        return n;
    }
    return fib(n-1) + fib(n-2);
}

bool can_sum_to_n(int n) {
    vector<int> fib_numbers;
    int i = 0;
    // Tính toán các số Fibonacci nhỏ hơn hoặc bằng n và đưa chúng vào một mảng
    while (true) {
        int fib_i = fib(i);
        if (fib_i > n) {
            break;
        }
        fib_numbers.push_back(fib_i);
        i++;
    }

    // Sử dụng phương pháp quy hoạch động để tìm các tổng con của các số trong mảng fib_numbers
    unordered_set<int> possible_sums = {0};
    for (int num : fib_numbers) {
        unordered_set<int> new_sums;
        for (int s : possible_sums) {
            new_sums.insert(s + num);
        }
        possible_sums.insert(new_sums.begin(), new_sums.end());
    }

    // Kiểm tra xem có tồn tại một tổng con bằng n hay không
    return possible_sums.count(n) && possible_sums.size() > 1;
}

int main() {
    // Ví dụ sử dụng
    cout << can_sum_to_n(7) << endl; // 1 (vì 7 = 5 + 2)
    cout << can_sum_to_n(10) << endl; // 1 (vì 10 = 8 + 2)
    cout << can_sum_to_n(12) << endl; // 0 (không có tổng con nào bằng 12)
    return 0;
}