Java backtrack


  • 0
    G
    public class Solution {
        
        int count = 0;
        
        public int triangleNumber(int[] nums) {
            int len = nums.length;
            if(len<3){
                return 0;
            }
            Arrays.sort(nums);
            
            backtrack(nums,0,0,0,0);
            return count;
        }
        
        public void backtrack(int[] nums, int index, int sideused, int sum, int cur){        
            if(sideused>3){
                return;
            }        
            //这里一定要是3,这样才能遍历完全部可能,如果是2,那么第三个数就只能到第二个数的index+1,不能到index+2或者更多。
            if(sideused==3 && sum-cur>cur){
               
                count++;
                return;
            }
            for(int i=index;i<nums.length;i++){
                if(i>=nums.length || sideused>=3){
                    return;
                }
                if(nums[i]==0){
                    continue;
                }           
                backtrack(nums,i+1,sideused+1,sum+nums[i],nums[i]);    
            }
        }
        
        
    }
    

Log in to reply
 

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