-
Notifications
You must be signed in to change notification settings - Fork 896
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
请用算法实现,从给定的无序、不重复的数组data中,取出n个数,使其相加和为sum。并给出算法的时间/空间复杂度。(不需要找到所有的解,找到一个解即可) #902
Comments
经典回溯法 function isValid(item, track) { function backtrack(nums, track, sum1) {
} backtrack(array, [], 0) |
function getResult(data, n, sum, temp = []) {
if (temp.length === n) {
const isExist = temp.reduce((accu, cur) => accu + cur, 0) === sum;
if (isExist) return temp;
return false;
}
let result = [];
for (let i = 0, len = data.length; i < len; i++) {
const current = data.shift();
temp.push(current);
result = getResult(data, n, sum, temp);
if (result) break;
// 还原为原数组
temp.pop();
data.push(current);
}
return result;
}
const arr = [1, 5, 6, 2, 4, 7, 3];
console.log(getResult(arr, 3, 10, [])); |
回溯算法 // n数之和
function nSum(arr = [], target, n) {
const set = new Set()
let result = null
function backTack(currArr, currSum, currIndex) {
// 回溯终止条件
if (currSum === target && currArr.length === n) {
result = [...currArr]
return
}
for (let i = currIndex; i < arr.length; i++) {
// 如果这个数之前已经使用过了,那直接跳过
if (set.has(arr[i])) continue
currArr.push(arr[i])
set.add(arr[i])
backTack(currArr, currSum + arr[i], currIndex + 1)
// 回溯
currArr.pop()
set.delete(arr[i])
}
// 没有找到结果
return null
}
backTack([], 0, 0)
return result
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
No description provided.
The text was updated successfully, but these errors were encountered: