バックトラックで 1 つずつしか使えない数から足すと目標になる組を全部集める

def combination_sum_once(
    candidates, target
):
    a = sorted(candidates)
    n = len(a)
    out = []
    path = []

    def dfs(s, left):
        if left == 0:
            out.append(path[:])
            return
        # この段で最後に選んだ額面
        prev = None
        for i in range(s, n):
            x = a[i]
            if x > left:
                break
            if x == prev:
                continue
            prev = x
            path.append(x)
            dfs(i + 1, left - x)
            path.pop()

    dfs(0, target)
    return out

function combinationSumOnce(
  candidates, target
) {
  const a = [...candidates];
  a.sort((p, q) => p - q);
  const out = [];
  dfs(a, 0, target, [], out);
  return out;
}

function dfs(
  a, s, left, path, out
) {
  if (left === 0) {
    out.push([...path]);
    return;
  }
  // この段で最後に選んだ額面
  let prev = null;
  const n = a.length;
  for (let i = s; i < n; i++) {
    const x = a[i];
    if (x > left) {
      break;
    }
    if (x === prev) {
      continue;
    }
    prev = x;
    path.push(x);
    dfs(a, i + 1, left - x,
      path, out);
    path.pop();
  }
}

import "sort"

func combinationSumOnce(
	candidates []int, target int,
) [][]int {
	a := []int{}
	a = append(a, candidates...)
	sort.Ints(a)
	n := len(a)
	out := [][]int{}
	path := []int{}
	var dfs func(s, left int)
	dfs = func(s, left int) {
		if left == 0 {
			p := []int{}
			p = append(p, path...)
			out = append(out, p)
			return
		}
		// この段で最後に選んだ額面
		prev := 0
		for i := s; i < n; i++ {
			x := a[i]
			if x > left {
				break
			}
			if x == prev {
				continue
			}
			prev = x
			path = append(path, x)
			dfs(i+1, left-x)
			path = path[:len(path)-1]
		}
	}
	dfs(0, target)
	return out
}