题解 | 数字游戏

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int findMinUnreachable(vector<int>& nums) {
        int n = nums.size();
        // 先排序，便于优化
        sort(nums.begin(), nums.end());
        
        // 记录可以表示的和
        vector<bool> dp(1000001, false);
        dp[0] = true;  // 空集和为0
        
        // 枚举所有子集
        for (int i = 0; i < (1 << n); i++) {
            long long sum = 0;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) {
                    sum += nums[j];
                }
            }
            if (sum <= 1000000) {
                dp[sum] = true;
            }
        }
        
        // 找到第一个不能表示的数
        for (int i = 1; i <= 1000000; i++) {
            if (!dp[i]) {
                return i;
            }
        }
        
        return 1000001;
    }
};

int main() {
    int n;
    cin >> n;
    
    vector<int> nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    
    Solution solution;
    cout << solution.findMinUnreachable(nums) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public int findMinUnreachable(int[] nums) {
            int n = nums.length;
            // 先排序，便于优化
            Arrays.sort(nums);
            
            // 记录可以表示的和
            boolean[] dp = new boolean[1000001];
            dp[0] = true;  // 空集和为0
            
            // 枚举所有子集
            for (int i = 0; i < (1 << n); i++) {
                long sum = 0;
                for (int j = 0; j < n; j++) {
                    if ((i & (1 << j)) != 0) {
                        sum += nums[j];
                    }
                }
                if (sum <= 1000000) {
                    dp[(int)sum] = true;
                }
            }
            
            // 找到第一个不能表示的数
            for (int i = 1; i <= 1000000; i++) {
                if (!dp[i]) {
                    return i;
                }
            }
            
            return 1000001;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        
        Solution solution = new Solution();
        System.out.println(solution.findMinUnreachable(nums));
        
        sc.close();
    }
}

class Solution:
    def find_min_unreachable(self, nums: list) -> int:
        n = len(nums)
        # 先排序，便于优化
        nums.sort()
        
        # 记录可以表示的和
        dp = [False] * 1000001
        dp[0] = True  # 空集和为0
        
        # 枚举所有子集
        for i in range(1 << n):
            sum_val = 0
            for j in range(n):
                if i & (1 << j):
                    sum_val += nums[j]
            if sum_val <= 1000000:
                dp[sum_val] = True
        
        # 找到第一个不能表示的数
        for i in range(1, 1000001):
            if not dp[i]:
                return i
        
        return 1000001

def main():
    n = int(input())
    nums = list(map(int, input().split()))
    
    solution = Solution()
    print(solution.find_min_unreachable(nums))

if __name__ == "__main__":
    main()