LeetCode 40.组合总和 II

组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
注意：解集不能包含重复的组合。

方法一、回溯

由于题目要求解集不能包含重复的组合，因此和39.组合总和解法不同。

怎么去重呢？

优化剪枝方法：
在这里插入图片描述

Swfit

class Solution {
    var freq = [(Int, Int)]()//记录数字出现的频率，元组表示（Int，Int），第一个参数为数字，第二个参数为次数
    var ans:[[Int]] = [[Int]]()
    var sequence = [Int]()
    
    
    
    func combinationSum2(_ candidates: [Int], _ target: Int) -> [[Int]] {
        
        let candi = candidates.sorted()
        
        for val in candi {
            if freq.isEmpty || val != freq.last!.0 {
                freq.append((val, 1))
            }else {
                let cnt = freq.last!.1 + 1
                let _ = freq.popLast()
                freq.append((val, cnt))
            }
        }
        
        dfs(0, target)
        
        return ans
    }
    
    func dfs(_ pos: Int, _ rest: Int) {
        
        if rest == 0 {
            ans.append(sequence)
            return
        }
        
        if pos == freq.count || rest < freq[pos].0 {
            return
        }
        
        dfs(pos+1, rest)
        
        
        let most = min(rest/freq[pos].0, freq[pos].1)
        if most == 0 {
            return
        }
        
        for i in 1...most {
            sequence.append(freq[pos].0)
            
            dfs(pos+1, rest-i*freq[pos].0)
        }
        
        for _ in 1...most {
            let _ = sequence.removeLast()
        }
    }
}

OC

#import "Number40.h"

@interface Number40 ()

@property (nonatomic, strong) NSMutableArray <NSArray *>*freq;
@property (nonatomic, strong) NSMutableArray *sequece;
@property (nonatomic, strong) NSMutableArray <NSArray *>*ans;

@end


@implementation Number40

- (instancetype)init {
    self = [super init];
    if (self) {
        _freq = [NSMutableArray array];
        _sequece = [NSMutableArray array];
        _ans = [NSMutableArray array];
    }
    return self;
}

- (NSArray *)combinationSum:(NSArray *)candidates target:(NSInteger)target {
    candidates = [candidates sortedArrayUsingComparator:^NSComparisonResult(NSNumber * obj1, NSNumber *obj2) {
        return [obj1 compare:obj2];
    }];
    
    //记录每个数据出现的次数
    for (NSNumber *num in candidates) {
        NSInteger inte = [num integerValue];
        if (_freq.count == 0 || [_freq.lastObject[0] integerValue] != inte) {
            [_freq addObject:@[num, @1]];
        }else {
            NSInteger cnt = [_freq.lastObject[1] integerValue] + 1;
            [_freq removeLastObject];
            [_freq addObject:@[num, @(cnt)]];
        }
    }
    
    [self dfs:0 rest:target];
    
    return self.ans;
}

- (void)dfs:(NSInteger)pos rest:(NSInteger)rest {
    if (rest == 0) {
        [self.ans addObject:self.sequece];
        return;
    }
    
    if (pos == self.freq.count || rest < [self.freq[pos].firstObject integerValue]) {
        return;
    }
    
    [self dfs:pos+1 rest:rest];
    
    NSInteger most = MIN(rest/[self.freq[pos].firstObject integerValue], [self.freq[pos].lastObject integerValue]);
    for (NSInteger i = 1; i<=most; i++) {
        [self.sequece addObject:self.freq[pos].firstObject];
        
        [self dfs:pos+1 rest:rest-i*[self.freq[pos].firstObject integerValue]];
    }
    
    for (NSInteger i = 1; i<=most; i++) {
        [self.sequece removeLastObject];
    }
}

@end