-
Notifications
You must be signed in to change notification settings - Fork 3
/
index.js
90 lines (88 loc) · 2.13 KB
/
index.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
* @lc app=leetcode id=40 lang=javascript
*
* [40] Combination Sum II
*
* https://leetcode.com/problems/combination-sum-ii/description/
*
* algorithms
* Medium (39.77%)
* Total Accepted: 197.3K
* Total Submissions: 495.3K
* Testcase Example: '[10,1,2,7,6,1,5]\n8'
*
* Given a collection of candidate numbers (candidates) and a target number
* (target), find all unique combinations in candidates where the candidate
* numbers sums to target.
*
* Each number in candidates may only be used once in the combination.
*
* Note:
*
*
* All numbers (including target) will be positive integers.
* The solution set must not contain duplicate combinations.
*
*
* Example 1:
*
*
* Input: candidates = [10,1,2,7,6,1,5], target = 8,
* A solution set is:
* [
* [1, 7],
* [1, 2, 5],
* [2, 6],
* [1, 1, 6]
* ]
*
*
* Example 2:
*
*
* Input: candidates = [2,5,2,1,2], target = 5,
* A solution set is:
* [
* [1,2,2],
* [5]
* ]
*
*
*/
/**
* @param {number[]} candidates
* @param {number} target
* @return {number[][]}
*/
var combinationSum2 = function(candidates, target) {
const result = [];
candidates.sort((a, b) => a - b);
const result_map = {};
foundResult(candidates.length - 1, target, []);
function foundResult(index, target, cur_res) {
for (let i = index; i >= 0; i--) {
if (candidates[i] > target) {
continue;
}
if (candidates[i] === target) {
const res = ([target]).concat(cur_res);
const key = res.join('_');
if (!result_map[key]) {
result.push(res);
result_map[key] = true;
}
continue;
}
foundResult(i - 1, target - candidates[i], [candidates[i]].concat(cur_res));
}
}
return result;
};
console.log(combinationSum2([2,5,2,1,2], 5));
console.log(combinationSum2([10,1,2,7,6,1,5], 8));
module.exports = {
id:'40',
title:'Combination Sum II',
url:'https://leetcode.com/problems/combination-sum-ii/description/',
difficulty:'Medium',
}