求数组的所有子集

序言

在项目中，有时候我们需要求一个数组的所有子集。例如一个数组有三个元素，[a，b，c]，求该数组的所有子集。分别是{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}共有8个子集，如果该数组有4个元素，5个元素或者更多元素呢？

算法解析如下

因为求解子集有规律，所以我们可以采用递归的思路去实现

/**
 求数组所有子集

 @param array 原始数组
 @param numbers 数字数组 - 用于标识使用
 @param index 索引
 */
- (void)subElements:(NSArray *)array numbers:(NSMutableArray *)numbers index:(int)index {
    if (index == array.count) {
        NSMutableString *strM = [NSMutableString string];
        for (int i = 0; i < array.count; i++) {
            NSNumber *number = numbers[i];
            if (number.intValue == 1) {
                [strM appendString:array[i]];
            }
        }
        if (strM.length > 0) {
            NSLog(@"%@",strM);
        }
        return;
    }
    numbers[index] = [NSNumber numberWithInt:0];
    [self subElements:array numbers:numbers index:index + 1];
    numbers[index] = [NSNumber numberWithInt:1];
    [self subElements:array numbers:numbers index:index + 1];
}

外界直接传参数调用即可

NSArray *array = @[@"a",@"b",@"c",@"d",@"e"];
NSMutableArray *numbers = [NSMutableArray array];
for (int i = 0; i < array.count; i++) {
  [numbers addObject:[NSNumber numberWithInt:0]];
}
    
 [self subElements:array numbers:numbers index:0];

运行结果如下：

image.png

---

算法分析

image.png

通过控制台输出，我们发现当index == 5的时候，numbers 里面的数据是有规律的即呈现递增样式。

image.png

通过以上表格，我们可以很直观的看出组合规律，就是把位置为1的字母组合起来即可。

---

项目连接地址