本文共 2222 字，大约阅读时间需要 7 分钟。

Objective-C 实现

#import @interface SubsetSum : NSObject(void)findSubsetsWithSum:(NSArray)

Objective-C 实现

#import @interface SubsetSum : NSObject(void)
- (void)findSubsetsWithSum:(NSArray
   
    *)numbers targetSum:(NSNumber*)target;
   

这个接口定义了一个类 SubsetSum，用于找到数组 numbers 中所有子集的和等于 target 的子集。接下来，我们将详细解释实现思路。

递归方法的实现思路

为了找到所有子集的和等于给定目标值的子集，我们可以使用递归的方法。递归是一种非常适合解决子集和问题的方法，因为它可以自然地处理问题的分治特性。

递归函数的思路

递归实现代码

- (void)findSubsetsWithSum:(NSArray
   
    *)numbers targetSum:(NSNumber*)target {
    // 初始化当前和为0，路径为空
    NSNumber *currentSum = [NSNumber numberWithInt:0];
    NSArray *path = [NSArray array];
    [self recursiveFindSubsets:numbers target:target currentSum:currentSum path:path];
}
- (void)recursiveFindSubsets:(NSArray
    
     *)numbers target:(NSNumber*)target currentSum:(NSNumber*)currentSum path:(NSArray
     
      *)path {
    // 如果没有元素可以选择，检查当前和是否等于目标
    if (numbers.count == 0) {
        if ([currentSum intValue] == [target intValue]) {
            // 将当前路径添加到结果中
            [self addResultWithPath:path];
        }
        return;
    }
    // 取出当前元素
    NSNumber *currentElement = numbers[0];
    // 选择包含当前元素
    NSNumber *newSum = [NSNumber numberWithInt:([currentSum intValue] + [currentElement intValue])];
    NSArray *newPath = [path arrayByAddingObject:currentElement];
    [self recursiveFindSubsets:numbers.dropFirst() target:target currentSum:newSum path:newPath];
    // 选择不包含当前元素
    [self recursiveFindSubsets:numbers.dropFirst() target:target currentSum:currentSum path:path];
}
     
    
   

代码解释

递归算法的优势

总结

通过上述方法，我们可以轻松地找到数组中所有子集的和等于目标值的子集。递归方法的直观性和灵活性使其成为解决子集和问题的理想选择。