Java solution with backtracking


  • 2
    Q
    public class Solution {
        List<List<Integer>> results = new ArrayList<List<Integer>>();
        public List<List<Integer>> combine(int n, int k) {
            findResult(1, n, k, new ArrayList<Integer>());
            return results;
        }
        
        private void findResult(int start, int end, int k, List<Integer> combo){
            if (k == 0){
                List<Integer> result = new ArrayList<Integer>();
                result.addAll(combo);
                results.add(result);
                return;
            }
            int j = 1;
            for (int i=start;i<=end;i++){
                combo.add(i);
                findResult(start+j, end, k-1, combo);
                combo.remove(combo.size()-1);
                j++;
            }
        }
    }

  • 0
    L

    This solution takes more time. Below is the CPP version. :)

    vector<vector<int>> ans;
    
    void run_recursively(const vector<int> &_arr, const int start,
            const int end, const int count)
    {
            if (0 == count) {
                    ans.push_back(_arr);
                    return;
            }
    
            for (int iii = start; iii <= end; iii++) {
                    vector<int> arr = _arr;
                    arr.push_back(iii);
                    run_recursively(arr, iii + 1, end, count - 1);
            }
    }
    
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            ans.clear();
            run_recursively(vector<int>(), 1, n, k);
            return ans;
        }
    };

  • 0
    L

    Here is a more fast CPP version.

    // Reference: https://leetcode.com/discuss/43968/java-solution-with-backtracking
    void combine_backtrack_implement(vector<vector<int> > *_matrix, vector<int> *_nums,
            const int start, const int end, const int index, const int k)
    {
            if (index == k) {
                    _matrix->push_back(*_nums);
                    return;
            }
    
            for (int iii = start; iii <= end - k + index + 1; iii++) {
                    (*_nums)[index] = iii;
                    combine_backtrack_implement(_matrix, _nums, iii + 1, end, index + 1, k);
            }
    }
    
    class Solution {
    public:
        vector<vector<int>> combine(int n, int k) {
            vector<vector<int> > ans;
    
            if (k > n || k <= 0)
                    return ans;
    
            vector<int> nums(k, 0);
            combine_backtrack_implement(&ans, &nums, 1, n, 0, k);
            return ans;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.