[Java] minor optimization to beat 93%


  • 0
    public class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> lists = new ArrayList<>();
            getComb(1, n, k, new ArrayList<>(), lists);
            return lists;
        }
        
        private void getComb(int cur, int n, int k, List<Integer> tmp, List<List<Integer>> lists) {
            if (k == 0) {
                lists.add(new ArrayList<>(tmp));
            }else {
                for (int i = cur; i <= n; ++i) {
                    if (n - cur + 1 < k) return; // optimization here: if there are not enough numbers we can stop dfs
                    tmp.add(i);
                    getComb(i+1, n, k-1, tmp, lists);
                    tmp.remove(tmp.size() - 1);
                }
            }
        }
    }
    

Log in to reply
 

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