题解 | 幸运的袋子

幸运的袋子

https://www.nowcoder.com/practice/a5190a7c3ec045ce9273beebdfe029ee

解题思路

这是一个DFS搜索问题，需要找出所有满足和大于积的组合。代码中包含了一些巧妙的优化：

对于1的特殊处理
连续相同数字的跳过
基于当前和与积的关系进行剪枝

关键点：

特殊处理数字1
跳过连续重复数字
基于和与积的关系剪枝
排序优化搜索

代码

cpp
java
python

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    int dfs(vector<int>& nums, int pos, long long sum, long long product) {
        int count = 0;
        int i = pos;
        
        while (i < nums.size()) {
            // 当前和大于积，找到一个解并继续搜索
            if (sum + nums[i] > product * nums[i]) {
                count += 1 + dfs(nums, i + 1, sum + nums[i], product * nums[i]);
            }
            // 特殊处理1，因为1不会使积变大
            else if (nums[i] == 1) {
                count += dfs(nums, i + 1, sum + 1, product);
            }
            // 剪枝：当前数字使积大于和，后面更大的数字也一定不满足
            else {
                break;
            }
            
            // 跳过连续的相同数字
            while (i < nums.size() - 1 && nums[i] == nums[i + 1]) {
                i++;
            }
            i++;
        }
        
        return count;
    }
    
public:
    int luckyBags(vector<int>& nums) {
        sort(nums.begin(), nums.end());  // 排序便于处理重复和剪枝
        return dfs(nums, 0, 0, 1);
    }
};

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

import java.util.*;

public class Main {
    static class Solution {
        private int dfs(int[] nums, int pos, long sum, long product) {
            int count = 0;
            int i = pos;
            
            while (i < nums.length) {
                // 当前和大于积，找到一个解并继续搜索
                if (sum + nums[i] > product * nums[i]) {
                    count += 1 + dfs(nums, i + 1, sum + nums[i], product * nums[i]);
                }
                // 特殊处理1，因为1不会使积变大
                else if (nums[i] == 1) {
                    count += dfs(nums, i + 1, sum + 1, product);
                }
                // 剪枝：当前数字使积大于和，后面更大的数字也一定不满足
                else {
                    break;
                }
                
                // 跳过连续的相同数字
                while (i < nums.length - 1 && nums[i] == nums[i + 1]) {
                    i++;
                }
                i++;
            }
            
            return count;
        }
        
        public int luckyBags(int[] nums) {
            Arrays.sort(nums);  // 排序便于处理重复和剪枝
            return dfs(nums, 0, 0, 1);
        }
    }
    
    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.luckyBags(nums));
        
        sc.close();
    }
}

class Solution:
    def dfs(self, nums: list, pos: int, sum_val: int, product: int) -> int:
        count = 0
        i = pos
        
        while i < len(nums):
            # 当前和大于积，找到一个解并继续搜索
            if sum_val + nums[i] > product * nums[i]:
                count += 1 + self.dfs(nums, i + 1, sum_val + nums[i], product * nums[i])
            # 特殊处理1，因为1不会使积变大
            elif nums[i] == 1:
                count += self.dfs(nums, i + 1, sum_val + 1, product)
            # 剪枝：当前数字使积大于和，后面更大的数字也一定不满足
            else:
                break
            
            # 跳过连续的相同数字
            while i < len(nums) - 1 and nums[i] == nums[i + 1]:
                i += 1
            i += 1
        
        return count
    
    def lucky_bags(self, nums: list) -> int:
        nums.sort()  # 排序便于处理重复和剪枝
        return self.dfs(nums, 0, 0, 1)

# 读取输入
n = int(input())
nums = list(map(int, input().split()))

solution = Solution()
print(solution.lucky_bags(nums))