M18155: 组合乘积

dfs, brute force, http://cs101.openjudge.cn/pctbook/M18155/

给定整数集合S和一个目标数T，判断是否可以从S中挑选一个非空子集，子集中的数相乘的乘积为T。

输入

输入为两行。第一行为目标数T。第二行为S中的N个元素，以空格隔开。其中 N <= 16。

输出

如果可以，则输出YES，否则输出NO。

样例输入

Sample Input 1:
12
1 2 3 4 5

Sample Output 1:
YES

样例输出

Sample Input 2:
33
4 2 8 7 5

Sample Output 2:
NO

提示

tag: dfs, brute force

来源

cs101-2017 期末机考备选

python

T = int(input())

data = input()
S = [int(ele) for ele in data.split()]

def DFS(S, T, cur_state, is_null, cur_pos):
    if is_null == False and cur_state  - T== 0:
        return True

    if cur_pos == len(S):
        return False

    if DFS(S, T, cur_state * S[cur_pos], False, cur_pos + 1):
        return True

    if DFS(S, T, cur_state, is_null, cur_pos + 1):
        return True

    return False

if DFS(S, T, 1, True, 0):
    print("YES")
else:
    print("NO")

分析一下题目：

集合 (S) 大小最多 16，直接暴力/DFS 枚举所有非空子集最多 (2^{16} = 65536)，完全可行。
思路：递归 DFS（或回溯），每个数可以选或不选。
注意：必须保证至少选一个数。
剪枝：如果当前乘积超过目标值 (T) 且 (T > 0)，可以提前返回；另外如果 (T = 0)，要特殊处理（只要有一个数是 0 就可以）。

Python 实现 (DFS 回溯)

python

def dfs(nums, idx, product, chosen, T):
    # 如果已经到达末尾
    if idx == len(nums):
        # 必须选过至少一个数
        return chosen and product == T
    
    # 不选当前数
    if dfs(nums, idx + 1, product, chosen, T):
        return True
    
    # 选当前数
    if dfs(nums, idx + 1, product * nums[idx], True, T):
        return True
    
    return False


def main():
    T = int(input().strip())
    nums = list(map(int, input().split()))
    
    if dfs(nums, 0, 1, False, T):
        print("YES")
    else:
        print("NO")

if __name__ == "__main__":
    main()

思路小结

用 dfs(idx, product, chosen) 表示考虑到第 idx 个数时的状态。
chosen 确保至少选了一个数，避免空集乘积等于 1 时误判。
时间复杂度 O(2^N)，N=16 时性能足够。

M18155: 组合乘积 ​

M18155: 组合乘积