k Sum II

Description

Given n unique integers, number k (1<=k<=n) and target.

Find all possible k integers where their sum is target.

Example
Given [1,2,3,4], k = 2, target = 5. Return:
[
  [1,4],
  [2,3]
]

Link

Lintcode_ladder

Method

1. dfs find all possible combination, then perform pruning
2. x

Example

1. 1

class Solution {
public:
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return a list of lists of integer 
     */
    vector<vector<int>> kSumII(vector<int> nums, int k, int target) {
        // write your code here
        // dfs, combination
        vector<vector<int>> result;
        if (nums.empty()) {
            return result;
        }
        vector<int> row;
        dfs(nums, result, row, k, target, 0);
        return result;
    }
    void dfs(vector<int>& nums, vector<vector<int>>& result, vector<int>& row, 
        int k, int target, int start
    ) {
        // find the combination
        // we dont care @param start, here start is just for rest for operation
        if (k == 0 && target == 0) {
            result.push_back(row);
            return;
        }
        // pruning 
        // start is for this time for
        if (k < 0 || target < 0 || start  >= nums.size()) {
            return;
        }
        // combination contribute
        int len = nums.size();
        for (int i = start; i < len; ++i) {
            row.push_back(nums[i]);
            dfs(nums, result, row, k - 1, target - nums[i], i + 1);
            row.pop_back();
        }
        return;
    }
};

Similar problems

x

Tags

x