from typing import (
    List,
)

class Solution:
    """
    @param a: an integer array
    @param k: a postive integer <= length(A)
    @param target: an integer
    @return: A list of lists of integer
             we will sort your return value in output
    """
    def k_sum_i_i(self, a: List[int], k: int, target: int) -> List[List[int]]:
        # write your code here
        if not a:
            return []

        self.ans = []
        self.dfs(a, k, target, [], 0)
        return self.ans

    def dfs(self, a, k, target, path, start_idx):

        # end of recursion
        if k <= 0:
            if sum(path) == target:
                self.ans.append(list(path)) # deepcopy
            return

        # define and split
        for idx in range(start_idx, len(a)):
            path.append(a[idx])
            self.dfs(a, k-1, target, path, idx+1)
            path.pop() # backtracking