Combination Sum at NVIDIA — Interview Guide

• Sort candidates first so you can prune when the running sum exceeds the target.
• Recurse with the same index (unlimited use) but never go back to an earlier index (avoids permutations of the same combo).
• Copy the current combination before adding it to the result.

def combination_sum(cands, target):
    cands.sort()
    res = []
    def bt(start, path, total):
        if total == target:
            res.append(list(path)); return
        for i in range(start, len(cands)):
            if total + cands[i] > target: break
            path.append(cands[i])
            bt(i, path, total + cands[i])
            path.pop()
    bt(0, [], 0)
    return res

• Low-level fluency — memory, caches, concurrency, SIMD.
• Performance mindset — profile, optimize, and reason about bottlenecks.
• Domain depth for the team (graphics, ML infra, autonomous systems).
• Collaboration across hardware and software boundaries.