剪枝优化技巧 ​

function combinationSum(candidates: number[], target: number) {
  candidates.sort((a, b) => a - b);
  
  function backtrack(start: number, sum: number, path: number[]) {
    if (sum === target) {
      result.push([...path]);
      return;
    }
    
    for (let i = start; i < candidates.length; i++) {
      // 剪枝：sum + candidates[i] > target
      if (sum + candidates[i] > target) break;
      
      path.push(candidates[i]);
      backtrack(i, sum + candidates[i], path);
      path.pop();
    }
  }
}

function permuteUnique(nums: number[]): number[][] {
  nums.sort((a, b) => a - b);
  
  function backtrack(path: number[], used: boolean[]) {
    // ...
    
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      
      // 剪枝：跳过重复元素
      if (i > 0 && nums[i] === nums[i-1] && !used[i-1]) {
        continue;
      }
      
      path.push(nums[i]);
      used[i] = true;
      backtrack(path, used);
      used[i] = false;
      path.pop();
    }
  }
}

let minCount = Infinity;

function backtrack(start: number, sum: number, path: number[]) {
  if (sum === target) {
    minCount = Math.min(minCount, path.length);
    return;
  }
  
  // 剪枝：当前路径已经不可能更优
  if (path.length >= minCount) return;
  
  // ...
}