手机可播放的网站,南京制作手机网站,华夏运用网站,网站建设公司推荐5788组合总和 II 给定一个候选人编号的集合 candidates 和一个目标数 target #xff0c;找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意#xff1a;解集不能包含重复的组合。 方法一、回溯
由于题目要求解集…组合总和 II 给定一个候选人编号的集合 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。 candidates 中的每个数字在每个组合中只能使用 一次 。 注意解集不能包含重复的组合。 方法一、回溯
由于题目要求解集不能包含重复的组合因此和39.组合总和解法不同。
怎么去重呢 优化剪枝方法
Swfit
class Solution {var freq [(Int, Int)]()//记录数字出现的频率元组表示IntInt第一个参数为数字第二个参数为次数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 1let _ 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(pos1, 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(pos1, rest-i*freq[pos].0)}for _ in 1...most {let _ sequence.removeLast()}}
}OC
#import Number40.hinterface Number40 ()property (nonatomic, strong) NSMutableArray NSArray **freq;
property (nonatomic, strong) NSMutableArray *sequece;
property (nonatomic, strong) NSMutableArray NSArray **ans;endimplementation 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:pos1 rest:rest];NSInteger most MIN(rest/[self.freq[pos].firstObject integerValue], [self.freq[pos].lastObject integerValue]);for (NSInteger i 1; imost; i) {[self.sequece addObject:self.freq[pos].firstObject];[self dfs:pos1 rest:rest-i*[self.freq[pos].firstObject integerValue]];}for (NSInteger i 1; imost; i) {[self.sequece removeLastObject];}
}end
